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 **A**^{4} the table would have 10^{8}
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 **A**^{k} 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
*i*^{th} and *j*^{th} 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:**