Algorithms used by the UACalcator
Finding Cg(a,b): An (essentially) linear time algorithm for this
is given in [Freese 2008],
based on the work in the early 1970's of R. Tarjan and others.
Finding the TCT type set of an algebra: We follow a slightly modified version of the algorithm described in [Berman, Kiss, Prohle, Szendrei]. Also see my talk on this subject, which shows that algorithm runs in \(\|\mathbf A\|^3\) time.
Bounding the TCT type set of \(\mathbf V(A)\): This is explained here.
The Maltsev condition for a locally finite variety to have a difference term, Ross Willard. This is explained here.
Finding free algebras.: This is explained in the Notes on the Birkhoff Construction, pdf .
Testing primality: We follow the procedure given in [Clark, Davey, Pitkethly, Rifqui]. Let 0 and 1 be two elements of A. They show that A is primal if
- the \(n\) characteristic functions (1 at \(i\), 0 elsewhere) are \(\mathbf F(1)\)
- the subalgebra of \(\mathbf F(1)\) generated by these characteristic functions includes the identity map.
- the subalgebra of \(\mathbf A^4\) generated by (0,1,0,1) and (0,0,1,1) contains (0,0,0,1) [the meet operation].
Computing \([\alpha,\beta]\): We use the algorithm, due to Ross Willard, given in Proposition 4.1 of [DeMeo, Freese, Valeriote 2019].
References
- J. Berman, E. Kiss, P. Prohle, and A. Szendrei, The type set of a finitely generated variety, Discrete Math. 112(1993), 1-20.
- D. Clark, B. Davey, J. Pitkethly, D. Rifqui, Flat unars: the primal, the semi-primal and the dualisable, Algebra Universalis, 63(2010), 303-329.
- Ralph Freese, Computing Congruences Efficiently, Algebra Universalis, 59(2008), 337-343.
- R. Freese, Automated Lattice Drawing, Lecture Notes in Artificial Intelligence, 2961, Springer, Berlin, 2004, 112-127.
- R. Freese, Notes on the Birkhoff Construction, pdf .
- R. Freese, Bounds on the TCT type set of \(\mathbf V(A)\), \(A\) idempotent, pdf .
- R. Freese, Notes on centrality, pdf .
-
Ralph Freese and Ralph McKenzie,
Commutator
theory for congruence modular varieties, 2nd edition.
A revised, online version.
- Ralph Freese and Matthew Valeriote, On the complexity of some Maltsev conditions, Intern. J. Algebra & Computation, 19(2009), 41-77.
- William DeMeo, Ralph Freese and Matthew Valeriote, Polynomial-time tests for difference terms in idempotent varieties, Intern. J. Algebra & Computation, 29(2019), 927-949.
- D. Hobby and R. McKenzie,
The Structure of Finite Algebras
Comtemporary Math.,
AMS, Providence, RI, 1988.
This is online:
http://www.ams.org/online_bks/conm76/. There is also the
complete book here.