The Universal Algebra Calculator is a mathematical program. It performs computations related to general algebraic structures.

Authors:

- Ralph S. Freese (ralph@math.hawaii.edu)
- Emil W. Kiss (ewkiss@cs.elte.hu)

- Main features and availability
- Getting the program
- Installation
- Compiling the program from sources
- Using the program
- Hints for using the graphical part
- Troubleshooting
- Mailing list
- History and acknowledgments

The present version has the following math functionalities:

- Form direct products.
- Create a factor algebra.
- Generate a subalgebra in a direct power.
- Create free algebras in a finitely generated variety.
- Compute the congruence lattice of an algebra.
- Compute the Tame Congruence Theoretic type labeling.
- Compute four types of centrality.
- Compute all unary polynomials.
- Compute minimal neighborhoods.

The program has a Graphical User Interface to access these functionalities via menus. In addition, this interface provides the facilities to

- Create and edit algebras using operation tables.
- Display the labeled congruence lattice graphically.
- Interrupt calculations safely.
- Display results of older calculations.

The program also has a batch version that allows to

- Use it in a non-graphical environment.
- Do calculations remotely.

The program is available under UNIX and Microsoft Windows. It can be freely downloaded from any of the sites

`http://www.cs.elte.hu/~ewkiss/software/uaprog`

`http://www.math.hawaii.edu/~ralph/software/uaprog`

You can download the sources, and also executables for various platforms.

The program can be used as a **teaching aid**, for
example to display the lattice of divisors of an integer,
the lattice of normal subgroups of small groups, or to
generate subgroups in small groups.

The program is especially useful in finding reasonable conjectures in Tame Congruence Theory. For example, it can find skew congruences and weird subdirectly irreducible factors in subdirect squares of an algebra. (This activity corresponds to doing experiments in natural sciences!) It is reasonable to compute the congruence lattice of an algebra of up to 200 elements (unless the lattice itself is too big). This is sufficient, because many nontrivial questions can be modeled in the subdirect squares of algebras of ten elements or less.

The program is under the GNU General Public License (see the
file `COPYING`

). This essentially guarantees your
rights to share and distribute the program freely, together
with its source code. It forbids others to prevent you doing
this (for example, by copyrighting it behind your back). It
also forbids people to enhance this program and then sell
this derived work for money.

If you achieve results by using this program, please make a reference to the program in the References section of your paper. We are writing a short paper about the program jointly with Matt Valeriote and whoever else contributes to it, and ask you to refer to this paper.

If you only want to **use** the program, it is sufficient
to download the **executables** from any of the sites
listed above. These are available for the following
platforms.

for Microsoft Windows, and

for Linux on Intel/AMD platforms that support rpm, and where you have root privileges.

You may also want to get the file `test_algebras.zip`

or
`test_algebras.tar.gz`

, depending on your
platform. In all other cases, you have to get the
**sources**, and compile the program yourself. See the
instructions in the
section about compilation.

The program is written using the Java programming language, and some parts are written in C. To run a Java-program on any computer, you have to download the Java Runtime Environment, or JRE for short. If you download and install this environment, then you can run any Java application, not just this program.

Note that if you also want to compile Java programs, or even the C part of the present program, you have to download the Java Software Development Kit instead, which contains the JRE. See the details in the section about compilation.

There are several vendors who produced a JRE. These may differ in performance. The one provided by Sun can be downloaded from

Here you can find the JRE for Solaris, Linux and Microsoft Windows, and also installation instructions.

**YOU MUST DOWNLOAD VERSION 1.3.1 OF THE ENVIRONMENT**
for the Calculator to work normally. Please, do not use
version 1.4.0 beta.

If you are using Linux, then we strongly recommend that you use instead the JRE manufactured by IBM Corporation, because that will execute the program much faster (which may be important in lengthy calculations). This is available from

`http://www-106.ibm.com/developerworks/java/jdk/linux130/jre-info.html`

You have to register (which is free) and fill out a form in order to download this version of the JRE. You should get version 1.3.0 (or later).

Depending on your Linux distribution, a JRE may have already been installed on your machine. If so, please make sure that its version is sufficiently recent. Make sure also that if you install the JRE that you downloaded, then it is this downloaded version that your machine uses by default.

If your Linux distribution supports the rpm Red Hat Package Manager (the most popular ones like Red Hat, SuSE do), then simply type as a superuser the following command:

`rpm -ivh uacalc-1.0.1-1.i386.rpm`

Make sure that the `PATH`

(of all ordinary users)
contains `/usr/local/bin`

(by editing scripts in
`/etc`

if necessary).

Installation is now complete. Every user on your system can use the program now by switching to a directory where he wants to store the algebra files, and typing

`UACalc`

This must be done under XWindows.

We assume that you want to use drive `C:`

(but
you can use any other drive, too). Copy the file
`uacalc-101_bin.zip`

to `C:\`

, and
unzip it with `winzip`

, or with
`pkunzip`

:

`C:\> pkunzip -d uacalc-101_bin.zip`

This will create a subdirectory
`C:\UACALC`

. Next, make sure that your PATH
contains this subdirectory. For example, type

`C:\> PATH=C:\UACALC;%PATH%`

You may want to put this line into your
`AUTOEXEC.BAT`

.

To run the program, open a DOS window, switch to a directory where you want to store your algebras, and type

`UACALC`

You need to run the program from a DOS window, because messages may be written there. The program itself will have separate windows, so do not use the DOS window in full screen mode.

The sources are contained in the files

The contents of these two files are identical, only their
formats differ, so grab the `zip`

file for
Windows, and the `tar.gz`

file for UNIX. You may
save some work (and money) by downloading the file

as well. You may also want to get the file `test_algebras.zip`

or
`test_algebras.tar.gz`

, depending on your
platform.

Open up these packages using

`gzip -d uacalc-1.0.1.tar.gz`

`tar -xvf uacalc-1.0.1.tar`

under UNIX, or by using winzip or pkunzip under Windows (make sure to keep the directory structure). Change to the directory

`uacalc-1.0.1`

under UNIX, and

`uacalc-101`

under Windows, respectively. That is the root of the source-tree.

Now you have to compile the Java part, and the C part.

The result of the compilation will be a file named `UACalc.jar`

. Therefore
**you can avoid this step**, if you download this file
(which is a binary that works on any platform).

If you want to recompile it, you need first to install the Java Software Development Kit (called JDK) for your platform (Solaris, Linux, Windows). These are available from Sun at

We do **NOT** recommend to use the IBM version for
compiling. Note that the JDK includes the JRE, so you do
not have to download that separately to actually run the
program. However, under Linux we still recommend to use the
IBM JRE to run the program for performance reasons.

To do the compilation, the following steps have to be performed:

- Use the
`javac`

command to compile all files named`*.java`

in all subdirectories of`src/uacalc`

and`src/javamath`

; - Use the
`jar`

command to create`UACalc.jar`

from the resulting classes.

Under Linux, this process is aided by a script: change to
the directory `src`

and run `./compile`

.

To compile the C part you still need the JDK, or at least
the C header files included in the JDK. Change to the
directory `src/C`

. You can find four makefiles
here:

`Makefile.linux`

is for normal Linux installations. It assumes that you installed the JDK in`/usr/local/jdk1.3.1`

. If not, edit the second line of this makefile accordingly. Then type`make -f Makefile.linux`

This produces two files:

`uab`

and`libua.so`

. Now switch back to the root of the source-tree, where you can find two scripts,`InstallAsRoot`

and`InstallAsUser`

. Run the first one as a superuser if you have root privileges. If you don't, you can still install the program locally by running`InstallAsUser`

(which will install it into the bin subdirectory of your home directory). Make sure that your`PATH`

contains`/usr/local/bin`

(for Root installs) and`$HOME/bin`

(for User installs). You can uninstall the program using the`Uninstall*`

scripts in this directory.`Makefile.solaris`

is for installation under Solaris. You will have to edit the`JDK_ROOT`

variable near the top of the file to point to the location of your JDK installation. Otherwise every step is the same as above. This makefile assumes that you use the GNU C-compiler`GCC`

. If not, you have to do further editing.`Makefile.Borland_windows`

is to compile the C part using the free*Borland Command-line C++ Compiler*(which can be downloaded from`http://www.borland.com/bcppbuilder/freecompiler`

after registering, which is free). This compiler includes a

`make`

utility, too. To compile, type`make -f Makefile.Borland_windows`

in the

`src/C`

subdirectory of the source-tree. Then, to install the program, create a subdirectory`C:\UACALC`

, and copy the files`uab.exe`

,`ua.dll`

,`*.bat`

to`C:\UACALC`

. Then copy`UACalc.jar`

to`C:\UACALC`

. Finally change to the root of the source-tree and copy`UACalc.bat`

to`C:\UACALC`

. Set your`PATH`

, and you are done.`Makefile.linux_dynamic`

is not intended for novice users. It is similar to`Makefile.linux`

, but links the executable`uab`

dynamically, and therefore requires that the shared library`libua.so`

be configured using`ldconfig`

. See the file`src/install_lib`

.

If you want to look at the code then please bear in mind
that **THIS IS A TEMPORARY VERSION**, which we wanted to
release fast so that you can use it. In later versions we
may change even the most basic classes. Most of the classes
are not yet documented properly in the present version. So
if you want to write your own extensions, please wait until
the next release, or contact us.

The program included in this distribution has two parts: the
graphical part (started by `UACalc`

) and the
batch part (started by `uab`

, or by scripts
described below). Most of the time you should probably use
the graphical part. This program has a graphical user
interface, and we hope that its use is self-explanatory. We
shall nevertheless give some hints on how to use it
below. **NOTE THAT THIS GRAPHICAL PART IS NOT INTENDED TO
BE RUN REMOTELY** (across a network), as its graphic
performance will degrade considerably.

The batch version has the advantage that it can be used without a graphical terminal (so you can log on to a fast machine and run it there). The two parts share the same data, so you can create an algebra with the graphical version, transform the files over, and do computations using the batch version.

Normally, programs written in C are 2-3 times faster than
ones written in Java. The batch version is written entirely
in C, the graphical part is written in Java, but uses some
of the routines of the C part. However, the graphical part
has improved algorithms for some of these calculations. All
in all, we recommend to stick with `UACalc`

when
possible. Note that the Linux version of the graphical part
is considerably faster than the Windows version (see the benchmarks below).

All data is stored on disk, both the algebras, and their computed invariants. If an invariant, like the congruence lattice, is computed, then it is stored on disk, and the next time it is read, instead of being computed. Therefore please do not manipulate these files by an editor, and do not delete them manually. Here are some tips for safely using the program.

- When trying to construct/investigate a particular example using the program, then create a new empty directory, and work there. It is safe to delete the contents of the entire directory. In fact, this is recommended, as the files generated can sometimes be really huge.
- Every algebra has a name. Say this name is
`z2`

, then all data related to this algebra are contained in files named`z2.*`

. (The operation tables are in`z2.alg`

, the congruences are in`z2.con`

, etc.) When you create a new algebra (like a subpower or a factor), then you have to give it a new name (like`z2_2`

for its direct square). It is safe to delete**all**related files (like deleting`z2.*`

). The program itself has a menu that does this. However, in this case the deleted algebras are saved under names like`z2.*.bak`

. So you can still recover accidentally deleted data. Thus it is safe to delete all files`*.bak`

, too. - It is also safe to delete the sometimes huge files
`*.log`

. However, these may contain details of calculations that are not displayed on the screen. Normally these details are not needed, but sometimes they help understanding the behavior of an algebra. - If you need to copy an algebra to a new directory, then
the simplest way is to copy all related files:
`copy z2.*`

, and not just`z2.alg`

. If you fear that the computed data is inconsistent (say after a system crash, or if you pulled the plug on the program), then try to copy`z2.alg`

,`z2.lck`

and`z2.dat`

, and discard the rest of`z2.*`

. If this still has problems, just keep`z2.alg`

. - The file
`z2.dat`

contains textual information about the algebra`z2`

. You can enter text freely when you create the algebra, and the main results of later calculations are written to this file. There is a menu which lets you display the contents of this file. However, you can also look at this file by any other tool, and you can even edit this file if you want to enter some crucial information you want to remember later, this is safe.

In the present version, all algebras are assumed to have underlying set {0,1,2,...,n-1} (where n is the size of the algebra). Thus editing and creating an algebra always consists of manipulating tables of integers. The names of the operations are also fixed, they are f0, f1, ... . Similarly, when computing the congruence lattice, the congruences are numbered from 0 to some integer in a random way. These same numbers are used when drawing the congruence lattice. Of course the program makes it possible to view the partition corresponding to any given congruence. In a later release we hope to provide symbolic names for objects (like elements of an algebra, or tuples, congruences, etc.).

You have to use the graphical part to create and edit
algebras. When that is done, and you have an algebra saved,
then you can quit the program `UACalc`

(if you
want), and use the following batch commands:

`centr` : |
compute centrality |

`cg` : |
generate a congruence |

`fact` : |
create a factor algebra |

`min` : |
compute minimal sets (used in Tame Congruence Theory) |

`p1` : |
compute all unary (and idempotent unary) polynomials |

`pra` : |
create a direct product |

`prc` : |
create a product congruence |

`spr` : |
generate a subalgebra in a direct power |

`typ` : |
compute a congruence lattice, and its TCT labeling. |

Type these commands without arguments to get help on how to
use them. Note that `cg`

and `typ`

are
not recommended to use, because the graphical part does
these calculations **much** faster. Also
`fact`

and `pra`

are not
time-critical. You do not gain time by using the batch
version of the commands `centr`

,
`min`

, `p1`

, `spr`

, because
the graphical part uses the same C routines as the batch
part to do these calculations.

The file `test_algebras.zip`

(or
`test_algebras.tar.gz`

) contains some example
algebras which you may use to test the program, or to learn
how to use it. Look at the `*.dat`

files for a
description of what is interesting in them. We call your
attention to `w4.alg`

, which is a 6 element
algebra whose congruence lattice contains all five TCT
types, and so it is worth displaying it to get familiar with
the colors!

The algebra `b2`

is a two element primal algebra,
and so the congruence lattice of its seventh direct power,
`b2_7`

, is isomorphic to a 128 element boolean
algebra. This congruence lattice, together with is type
labeling has been computed in

- 140 seconds under Linux, with the IBM JRE
- 216 seconds under Microsoft Windows, with the Sun JRE

on a 366 MHz AMD K6-2 processor with a 66 MHz FSB.

In order to use the basic features of the program, you should be aware of the rudiments of general algebra. There is a textbook that we recommend:

**S. Burris, H. P. Sankappanavar:** *A course in
Universal Algebra.*

It can be freely downloaded from

`http://www.thoralf.uwaterloo.ca/htdocs/ualg.html`

To understand the TCT-related features, you should consult the book

**D. Hobby, R. McKenzie:** *The structure of finite
algebras.*

Do not be surprised that when you bring up the *Algebra
Editor*, then the main frame of the program becomes
dead, and remains dead until you close the editor. This is
to prevent you to start any calculations on an algebra being
edited. In later versions we may relax this restriction
somewhat with a better locking mechanism. Please note
however that when you edit an algebra, then all results
computed so far about that algebra become invalid. The
program therefore deletes this data when you finish
editing. If you want to keep this data, then use the
`Save As`

menu when saving an edited existing
algebra for the first time, and select a new name.

When creating a new operation, the program lists all
possible arguments, and asks you to fill in the
corresponding value. It is difficult not to make an error
while doing this. Even if you realize that you made an
error, do not stop! Fill in all values, and then go to the
`Change values`

menu. This lets you edit (and
check) the table of the operation, and then you can correct
the mistakes.

When you edit a value of an operation, then the new value
you entered is not accepted by the program until you hit
`Enter`

. Even if you save while editing a cell,
the old value is saved! You can press `Escape`

to
cancel editing a cell. On the other hand, moving to another
cell with `Tab`

or the arrow keys confirms the
new value in the cell. The `Tab`

key is
especially useful when entering values fast (for example,
when entering generators of subpowers).

The `Compute/Stop`

menu lets you stop
calculations. This facility is not implemented yet for
**all** possible calculations. When a calculation is
stopped, the program informs you about this. During some
calculations the program gives you a progress report (like:
there are already 20000 congruences, or: it will take at
least 1000 more hours to finish this calculation). These are
the times to use the `Stop`

menu.

The most important part of the program is the *Congruence
Displayer*, which comes up when you use the
`Compute/Congruences`

menu.

**Do not always compute the congruence lattice.**
Originally the congruence lattice is not computed. There are
algebras, where this may not even be feasible to do. For
example, if you have a set of 10 elements, and no
operations, then the congruence lattice is too big to be
computed, but it may still be possible to compute other
invariants, like the TCT type set of the algebra. Even when
the congruence lattice is not computed you can

- generate congruences; display, join, and meet them;
- create factor algebras;
- compute the TCT type set.

You can compute the congruence lattice of the algebra by
using the `Lattice/Compute and Label`

menu. Then
the displayer window extends itself. Let us explain the four
boxes that appear. These are the ** MODE** box (top
left), the

The ** MODE** box lets you decide if you want to see

- all congruences
- all meet-irreducible congruences
- all join-irreducible congruences
- all principal congruences.

Whichever of these you select, the list of the corresponding
congruences appears in the ** LIST** box. Thus, for
example, if you are hunting for large subdirectly
irreducible factors, then select meet-irreducibles in the

The ** LIST** box has one

For example, suppose that you want to compute the minimal sets for the cover C3 -< C15. Then

- set the
box to "all congruences";*MODE* - select C3 in the
box (or via the Select menu);*LIST* - select "upper covers" in the
box;*COVER MODE* - select C15 in the
box.*COVER LIST*

Now at the right bottom corner you can already see the TCT
type of this quotient. The `Taming/Minimal sets`

menu will compute the minimal sets for this cover.

If there are many congruences, you may find it more
convenient to use the `Select`

menu to select
congruences instead of trying to locate them in the
** LIST** box.

**Math calculations**. You can compute meets and joins
via the `Lattice`

menu, and Centrality with the
`Centrality`

menu. See the paper

**K. A. Kearnes, E. W. Kiss:** *Finite Algebras of
Finite Complexity*

(that appeared in *Discrete Mathematics*) for the
meaning of weak and rectangular centrality.

If the congruence lattice is not too big, then we recommend
that you draw it graphically, using the
`Graphics/Drawer`

menu. This brings up a new
window, where the lattice is drawn. Hit the
`Improve`

button to get a better picture, unless
the lattice is too big.

The colors of the edges correspond to the TCT labeling:

- type 1: red
- type 2: yellow
- type 3: white
- type 4: blue
- type 5: black

Here are two hints to remember the colors: the richer types are lighter, and the solvable types have a red component.

The *Drawer* works in coordination with the
*Displayer*. The selected congruence is highlighted
(currently has a thick magenta
border), its displayed covers are green rather than black, and the selected cover is
thicker than the others. When you make a selection in the
** MODE** box, the corresponding congruences are
highlighted. You can change the selected congruence and the
selected edge by right-clicking on the corresponding point
or edge.

If the lattice is big, you may want to draw only an
interval. Click the `Interval`

button, and then
select the desired bottom with a left click, and the desired
top by a right click. You must do this in such a way that
the selected bottom element is strictly below the selected
top element. Then click `OK`

to get a drawing of
this interval. You can use all the features described above
on the drawn interval with the exception that selection in
the ** MODE** box provides no highlighting (the

It may happen that upon startup the program complains about
missing fonts, or about the inability to provide
`VirtualBinding`

for certain keyboard keys. These
are harmless messages (and signify problems with the JRE,
not with the program). You should ignore these messages
unless you have problems running the program itself.

**PLEASE MAIL ANY OTHER PROBLEMS, REQUESTS TO**

Emil W. Kiss: ewkiss@cs.elte.hu

Please do so even if you solved the corresponding problem. This helps us to improve the program, or the documentation. We may be able to to assemble a FAQ from your remarks. Also please inform us about successful/unsuccessful installations, etc.

The files generated by the program have the usual platform
dependent line ending characters. This may make editing
difficult (but the program `edit`

under Windows,
and `emacs`

under UNIX handles these problems
properly). We tried to make sure that the program reads the
files created on other platforms, so you can transfer
algebras from one computer to another.

You can subscribe to a mailing list in order to get information, and participate in discussions concerning the following topics.

- Abilities that you want the program to have;
- Effective algorithms for computations;
- Installation and usage problems on various platforms;
- Design issues, the future of the program;
- Offers to contribute programming efforts.

The address of the list is
`uaprog-l@matrix.newpaltz.edu`

. The automatic
way to subscribe is to send email to Majordomo@matrix.newpaltz.edu.
Please, include the line

`subscribe uaprog-l`

in the body of the message (preferably as the first line; the subject of the letter is not processed). If you include the line

`help`

then you get usage information concerning the list (for example, you can learn how to retrieve the archive containing all previous correspondence).

The first version of the program has been written by students of Matt Valeriote in 1988-91, for XWindows. This version had many of the features of the present program, and some additional ones, too, which we plan to implement. These include working with terms and identities, drawing subalgebra lattices, etc. However that version has many bugs. It is available from

`ftp://icarus.math.mcmaster.ca:/pub/UA/Algebra.tar.gz`

Many of the ideas for writing the present program came from that version. This old version had some partial MS-DOS ports, but these are now made obsolete by the present program.

The other source of inspiration has been Ralph Freese's lattice drawing program, which is integrated into the present program. It can display any lattice, not just congruence lattices. You can try out the original version online, or download the source. The address is

`http://www.math.hawaii.edu/~ralph/LatDraw`

The program makes use of Ralph Freese's algorithms concerning partitions, to speed up calculations. You can download the corresponding reprints from

`http://www.math.hawaii.edu/~ralph/papers.html`

Back to the top