Projekt A16 - Automatic, Hyperbolic and Related Semigroups

(Laufzeit: 02/2005 bis 01/2007)

Recent years have seen the development of a rich interplay between algebra and the theory of computer science. There are two closely related aspects to this trend: the use of techniques from formal language theory to describe certain classes of algebraic structures, and the study of algorithms for solving algebraic problems.

Perhaps the most significant example is provided by the theory of automatic, biautomatic and asynchronous automatic groups. These classes of groups are defined in an automata-theoretic manner, but also display a number of interesting geometric properties. An automatic structure for a group provides a means to address many algorithmic problems. For example, given an automatic structure for a group, one can solve the word problem for the group in quadratic time. Given a slightly stronger structure, known as a biautomatic structure, the conjugacy problem also become solvable.

While much recent work in this area concerns groups, there is an older connection between formal language theory and the more general theory of semigroups and monoids. Indeed, the study of formal languages can be thought of as the study of finitely generated free monoids, while the regular languages are exactly the homomorphic pre-images of subsets of finite monoids.

It is well known that the usual definition of an automatic group lends itself well to application to more general classes of algebras. For example, Epstein introduced automatic groupoids, as a means to show that fundamental groups of hyperbolic surfaces are automatic. More recently a number of authors have considered the extent to which the theory of automatic groups can be extended to incorporate semigroups and monoids, and the beginnings of a theory of automatic semigroups have emerged. Further, Kambites has provided a common framework for the generalisation to semigroups and to groupoids, by showing that many results about automatic semigroups generalise to semigroupoids and small categories.

Another important class of groups is the class of hyperbolic groups. Because of the inherently directed nature of semigroup Cayley graphs, there is no obvious way in which one can extend the usual geometric definition of hyperbolicity to describe a more general class of semigroups and monoids. However, in a significant recent development, Gilman has shown that the hyperbolic groups also have a language-theoretic characterisation. In particular, hyperbolic groups are exactly the groups for which some language of representatives has a context-free multiplication table. Duncan and Gilman have recently shown that this definition does naturally extend to describe a more general class of semigroups. The question arises of which of the special properties enjoyed by hyperbolic groups, are also enjoyed by hyperbolic semigroups.

Certain classes of semigroups (generally, those with some local notion akin to that of an inverse in groups) do admit a more geometric analysis than is generally the case. Examples include the completely-simple semigroups, and the inverse semigroups. Fountain and Kambites have shown that the class of completely simple semigroups admits the usual geometric definition of automaticity, and that this definition coincides with Gilman's word-hyperbolic one.

Still other classes of semigroups have been defined in a language-theoretic way, including the very large class of semigroups with rational cross-sections, and the rather smaller class of rational semigroups.

Our main objectives are threefold:

(i) To seek a better understanding of the relationship between the various classes of semigroups characterised by automata-theoretic conditions.

The classes of automatic semigroups, asynchronous automatic semigroups, biautomatic semigroups, prefix-automatic semigroups, word-hyperbolic semigroups, rational semigroups and semigroups with rational cross-section are clearly related in a rich and complex way. However, there is still a great amount of work to be done. The important class of prefix-automatic semigroups was not yet considered, and indeed a very important open question is that of whether the classes of prefix-automatic and automatic semigroups coincide. The research will also consider the intersections of these classes, and inclusions when attention is restricted to particular types of semigroups. For example, it is known that not all hyperbolic semigroups are automatic, but is a hyperbolic commutative semigroup necessarily automatic?

Also, associated to every inclusion question with a negative or unknown answer is a decision problem. For example, it is known that not every hyperbolic semigroup is automatic, but is there an algorithm to decide, given a hyperbolic structure for a semigroup, whether the semigroup is automatic? Furthermore, all of these classes are characterised by the existence of combinatorial structures with certain properties, so one can also aks, for example, whether given a hyperbolic structure for a semigroup, there is an algorithm to construct an automatic structure for the semigroup? We seek to answer at least some of these questions.

(ii) To establish the decidability and complexity of certain algorithmic problems concerning semigroups in these classes.

It is well-known that the classes of automatic and hyperbolic groups, and related groups, have interesting computational properties. For example, hyperbolic groups and automatic groups have word problems which are solvable in very fast (linear or quadratic) time, while biautomatic groups have solvable conjugacy problems.

Some of these results have been extended to the semigroup case. For example, it is known that hyperbolic semigroups have solvable word problems, while automatic groups have word problems solvable in quadratic time. However, very little is known about the decidability and complexity of other notable decision problems in these classes of monoids. Examples include the conjugacy problem, the isomorphism problem and decision problems expressible by linear sentences.

The research will endeavour to find algorithms for, or to prove undecidability of, these decision problem in the various classes of semigroups under consideration. We may also consider implementing any such algorithms in a computer language such as GAP.

(iii) To extend the results of objectives (i) and (ii) to the widest possible context.

In view of the work of Kambites, it is highly likely that some of the results found for semigroups under objectives (i) and (ii) will generalise in a straightforward manner to apply also in semigroupoids and small categories. Where possible, we shall seek such generalisations.

Supported by the EU under a Marie-Curie Intra-European Fellowship (MEIF-CT-2003-501068).


Mark Kambites, PhD
(jetzt: School of Mathematics, University of Manchester, England)

Technische Reports:

Kambites, M. and Otto, F.:
Church-Rosser groups and growing context-sensitive groups
Mathematische Schriften Kassel 7/06, Universität Kassel, August 2006.
Kambites, M. and Otto, F.:
Uniform decision problems in automatic semigroups


Kambites, M. and Otto, F.:
Uniform decision problems for automatic semigroups.
Journal of Algebra 2006, 303:789--809