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.