Projekt 18 - Monoide mit automatischer Struktur (Monoids with automatic structure)

(bis 12/2005)

In recent years the computational aspect has become more and more prominent in combinatorial group and semigroup theory. Although in general not much information on the algebraic structure presented can be extracted from a finite presentation, various methods have been used successfully in certain instances.

One approach is based on the notion of a convergent presentation. A monoid-presentation (\Sigma;R) is called convergent if the string-rewriting system R is convergent, that is, the reduction relation induced by R is both noetherian and confluent. The presentations of this form are of particular interest, because the reduction relation induced by a convergent string-rewriting system R yields a unique irreducible string for each congruence class of the Thue congruence generated by R. Hence, if a monoid M has a finite presentation of this form, then it has a decidable word problem. In fact, for the class of finite convergent presentations, the uniform word problem is decidable, which implies that for this class various decision problems can be solved that are undecidable in general. For example, the problem of deciding whether the monoid presented is actually a group is decidable for this class.

As an alternative to the rewriting approach Epstein et al developed the notion of groups with automatic structure during the 1980's. A finitely generated group G has an automatic structure if it has a finite set of generators \Sigma and a regular set S \subset \Sigma^* of representatives, which, however, need not be unique, such that the following tasks can be performed by finite state acceptors:

  1. Given two elements u,v \in S, decide whether or not they both represent the same element of the group G.
  2. For a \in \Sigma, if two elements u,v \in S are given, decide whether or not ua and v represent the same element of the group G.
Thus, an automatic structure provides a regular set of representatives for the group considered such that the group operation can be realized on these representatives through the finite automata of 2., which accordingly are called the multiplier automata.

Although the definition mentions explicitly a set of generators \Sigma for the group considered, it turns out that the existence of an automatic structure is independent of the finite set of generators chosen. Further, the word problem for each automatic group can be solved in quadratic time, and each automatic group has quadratic derivational complexity, that is, its Dehn function has a quadratic upper bound. Hence, automatic groups are hypberbolic. Finally, each automatic group is finitely presented and it satisfies the homological finiteness condition FP_\infty, and hence, each automatic group has finite derivation type.

If the group G has a finite convergent presentation (\Sigma;R), then the set of irreducible strings IRR(R) is a regular set of unique representatives for the group G, and so also condition 1. above is satisfied. But in general there need not exist multiplier automata in this situation. And indeed, there exist finitely presented groups that do admit finite convergent presentations, but that do not have an automatic structure. However, it is still not known whether each automatic group admits a finite convergent presentation.

Recently, the notion of automatic structure has been generalized to monoids. Automatic monoids do also have word problems that are decidable in quadratic time, but it turns out that for monoids the existence of an automatic structure does indeed depend on the actually chosen set of generators. Also an automatic monoid need not be finitely presented.

Here we are interested in determining algebraic, algorithmic, and combinatorial properties of (certain subclasses of) the class of automatic monoids.

Mitarbeiter:

Klaus Madlener
(Fachbereich Informatik, Universität Kaiserslautern)

Nik Ruskuc
(School of Mathematics and Statistics, University of St Andrews, St Andrews, Schottland)

Andrea Sattler-Klein

Interne Berichte:

Otto, F. and Ruskuc, N.:
Confluent monadic string-rewriting systems and automatic structures.
Mathematische Schriften Kassel 25/00, Universität-GH Kassel, Oktober 2000.
published in revised form in the Journal of Automata, Languages, and Combinatorics
Otto, F. :
On s-regular prefix-rewriting systems and automatic structures.
Mathematische Schriften Kassel 9/98, Universität-GH Kassel, September 1998.
Otto, F. :
On Dehn functions of finitely presented bi-automatic monoids.
Mathematische Schriften Kassel 8/98, Universität-GH Kassel, Juli 1998.
Otto, F. and Sattler-Klein, A. :
Some remarks on finitely presented monoids with automatic structure.
Mathematische Schriften Kassel 9/97, Universität-GH Kassel, August 1997.
results presented at RTA'98.

Veröffentlichungen:

Otto, F. and Ruskuc, N.:
Confluent monadic string-rewriting systems and automatic structures
Journal of Automata, Languages, and Combinatorics, 2001, 6:375-388
Otto, F.:
On Dehn functions of finitely presented bi-automatic monoids.
Journal of Automata, Languages, and Combinatorics, 2000, 5:405-419.
Otto, F.:
On s-regular prefix-rewriting systems and automatic structures.
In Asano, T. and Imai, H. and Lee, D.T. and Nakano, S. and Tokuyama, T., editors, Computing and Combinatorics, Proceedings {COCOON'99}, Lecture Notes in Computer Science 1627, pages 422-431, Springer-Verlag, Berlin, 1999.
Otto, F. and Sattler-Klein, A. and Madlener, K.:
Automatic monoids versus monoids with finite convergent presentations.
In Nipkow, T., editor, Rewriting Techniques and Applications, Proceedings RTA'98, Lecture Notes in Computer Science 1379, pages 32-46, Springer-Verlag, Berlin.