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.

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

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. Ralph Freese and Ralph McKenzie, Commutator theory for congruence modular varieties, 2nd edition. A revised, online version.

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

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