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].
The Calculator returns the \(n+2\) terms witnessing these. The paper shows how these terms can be combined to give every operation on \(A\). Basically this test has the complexity of computing \(\mathbf F(1)\).

Computing \([\alpha,\beta]\): We use the algorithm, due to Ross Willard, given in Proposition 4.1 of [DeMeo, Freese, Valeriote 2019].

More coming!

References

  1. J. Berman, E. Kiss, P. Prohle, and A. Szendrei, The type set of a finitely generated variety, Discrete Math. 112(1993), 1-20.

  2. D. Clark, B. Davey, J. Pitkethly, D. Rifqui, Flat unars: the primal, the semi-primal and the dualisable, Algebra Universalis, 63(2010), 303-329.

  3. Ralph Freese, Computing Congruences Efficiently, Algebra Universalis, 59(2008), 337-343.

  4. R. Freese, Automated Lattice Drawing, Lecture Notes in Artificial Intelligence, 2961, Springer, Berlin, 2004, 112-127.

  5. R. Freese, Notes on the Birkhoff Construction, pdf .

  6. R. Freese, Bounds on the TCT type set of \(\mathbf V(A)\), \(A\) idempotent, pdf .

  7. R. Freese, Notes on centrality, pdf .

  8. Ralph Freese and Ralph McKenzie, Commutator theory for congruence modular varieties, 2nd edition. A revised, online version.

  9. Ralph Freese and Matthew Valeriote, On the complexity of some Maltsev conditions, Intern. J. Algebra & Computation, 19(2009), 41-77.

  10. William DeMeo, Ralph Freese and Matthew Valeriote, Polynomial-time tests for difference terms in idempotent varieties, Intern. J. Algebra & Computation, 29(2019), 927-949.

  11. 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.