UACalc (Semi) Technical Description

We are in the process of rewriting the Universal Alebra Calculator, originally written by Matt Valeriote and revised by Emil Kiss and myself. This document describes the internal structure of algebras and operations. One of the major design goals is to have more flexibility in the representations of the algebras.

The original program represented operations as tables. If A has 10 elements and a binary operation, this table has 100 elements. But for A4 the table would have 108 elements. So we have direct product operations which work in the obvious way and these take up no additional space.

We also need to handle congruence lattices and subalgebra lattices which typically are too big to even calculate the number of elements, let alone hold them in memory. For the two element semilattice, the sizes of the congruence lattices of Ak are 2, 7, 61, 2480, ..., and so quickly become too big to hold in memory. However an n element algebra has at most n/2 principal congruences and the following can be quickly determined withour finding the whole congruence lattice:

  • If A is simple.
  • If A is subdirectly irreducible.
  • A subdirect decompostion of A into si's.
  • The TCT type set of A.

Big and Small Algebras

SmallAlgbra is a java interface. Roughly a small algebra is one who elements can be enumerated. Most of the algebras in the system will be SmallAlgebras. Congruence lattices and subalgebras lattices are not SmallAlgebras.

Underneath, SmallAlgebras are int based. The user can choose whatever he wants for the universe, say {0, a, b, c, 1}, but underneath there will be a map from this universe to {0, 1, 2, 3, 4} and all operations will be done on these ints and converted to the user's universe for output. So for example if C is the direct product of A and B, a binary operation will need to calculate the product of the ith and jth elements. It will first unwind i and j into ordered pairs using a Horner algorithm, multiply component wise, and use Horner again to convert back. There is a time penalty for this but there is a option for the operation to generated a table and use that. Of course the later has a space penalty.

Classes Implementing the SmallAlgebra interface

  • BasicAlgebra: This represents an algebra the user might define by operation tables. The user can supply a universe or just use {0, ..., n-1}.
  • ProductAlgebra: The direct product of a finite list of (not too many) algebras (meaning SmallAlgebras, of course). You can get the list of factors from a product algebra. Of course the universe is the direct product of the universes of the factors.
  • PowerAlgebra: The direct power of a SmallAlgebra.
  • QuotientAlgebra: The quotient of one algebra modulo a congruence. The super algebra (or pre-image) and the congruence are accessible. The congruence has a system of representative which effectively form the universe of the quotient. The operations act on this set of representative in the super algebra and take the representative of the result. As an explicit example, suppose the system of representatives is {2, 8, 13}. Then in the quotient to multiply 1 and 2 we multiply 8 and 13 in the super algebra and find the representative of the answer. If say this was 2, this quotient operation would return 0 (the index of 2 in the list of representatives). There is a special class for the elements of the universe of a quotient algebra so they can be written as a/\theta.
  • Subalgebra: This is similar to QuotientAlgebra. We keep the indices in the super algebra of the subuniverse and just use these to perform the operations.

Big Algebras

These represent algebras where it is impratical or impossilbe to index the elements. There is an Algebra interface and SmallAlgebra is a subinterface. (There is no BigAlgebra interface.) The operations act directly on the elements of the universe rather than on the indices. The universe of an algebra is an instance to the interface Set, which comes with java, stretch somewhat. The contains method should be implemented. The size() method, which should produce and int, gives a negative number if the size is unknown, or too big to be an int (for example if the algebra is infinite).

Using this, infinite algebras can be represented. For example, the universe of the free lattice on X would consist of lattice terms over X which are in canonical form.

The main two examples of big algebras are congruence lattices and subalgebra lattices.

  • CongruenceLattice: The elements are partitions and we use the algorithms outlined in my note on Partition Algorithms, which can be found on my Notes page.
  • SubalgebraLattice:

References

  1. Computing Congruences Efficiently, available at my papers.
  2. Partition Algorithms, available at my notes.