(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:
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.
Nik Ruskuc
(School of Mathematics and Statistics, University of St Andrews, St Andrews, Schottland)
Andrea Sattler-Klein