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

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)$$.

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