GASP at the University of Nebraska

At the initial GASP planning meeting it was decided to rewrite the Automate package to make it more efficient and also useful to group theorists.

The new features of the Automate package include facilities for producing the inverse automaton naturally associated to a finite set of generators for a subgroup of a free group, facilities for determining a minimal set of generators for such a finitely generated subgroup from the associated automaton and a Todd-Coxeter enumeration algorithm for inverse semigroups. All of this is integrated with Automate's transformation semigroup package and is used to answer algorithmic questions about finitely generated subgroups of free groups and finitely presented inverse semigroups.

We began work on the integration of GASP and Automate on September 1, 1995. (It took a year to resolve administrative problems connected with funding a programmer at UNL.) Integrating Automate's existing regular operations into the GASP project is going according to the following four step plan:

  1. Create C++ classes for automata and alphabets capable of representing the various structures in the current GASP standard file format document,
  2. Implement GASP file I/O for these classes,
  3. Implement translations between this new internal representation and Automate's original internal representation, and
  4. Add a new top-level interface to Automate, allowing processing to be directed from the command line.
Presently we have completed steps 1 and 2 of the plan. Steps 3 and 4 are largely trivial, placing us more than half-way to our goal of having Automate available from the command-line for integration with other GASP systems, as well as in the form of a C++ class library.

Currently, we have C++ classes for dense internal representations of automata, for abstract automata (to facilitate alternate storage strategies later) and the various alphabetic types mentioned in the GASP preliminary standard document. We also have rudimentary I/O facilities employing the format of the GASP document. A parser for translation between Automate and GASP formats has been written. Work has begun on translating the regular operations for automata and on building a command-line interface, that would allow us to become a GAP package.