Relationships between different computational classes of monoids.
Speaker: Dr Michael Hoffmann, Department of Computer Science, School of Mathematics and Computer Science, Uni
When: 2003-08-20 10:00:00
Venue: 78-622
Host: George Havas
Abstract:The talk includes joint work with Dietrich Kuske, Fred Otto and Rick Thomas.
The concept of an automatic group was introduced in the early 1990's
in order to describe a large class of naturally occurring groups
with an easily solvable word problem. This notion was then extended
to automatic monoids. In both cases the defining property is the
existence of a regular set of normal forms (with respect to some
finite generating set A) such that we have a finite automaton with
two input tapes that can verify whether two normal forms represent
the same monoid element, and, for each generator in A, a finite
automaton that can determine whether one normal form represents the
monoid element that corresponds to the other normal form multiplied
by the generator in question. According to whether the two input
tapes are read synchronously or asynchronously, one distinguishes
between automatic and asynchronously automatic monoids.
An important subclass of the class of automatic groups is that of
``hyperbolic'' groups. Recently, Gilman gave an elegant
characterization of hyperbolic groups in terms of pushdown automata.
Again, one requires the existence of a regular set of normal forms
(over some finite generating set); in this case the pushdown
automaton reads three normal forms in sequel and decides whether the
third represents the product of the first two. This
characterization of hyperbolic groups, unlike many of the others,
extends easily to monoids giving rise to the notion of hyperbolic
monoids. We will see, however, that, whilst hyperbolic groups are
necessarily automatic, this implication no longer holds when we
generalize to monoids.
A fourth class of monoids that can be described in this sort of way
is the class of ``rational'' monoids. Here one requires the
existence of a set of unique normal forms (over some finite
generating set) such that the normal form of any word can be
computed by a finite transducer (i.e. a finite automaton with
output). So, as in the other notions, we have a regular set of
normal forms. Unlike the other concepts considered here, which were
first defined for groups and then generalized to monoids, the notion
of being rational was first defined by Sakarovitch in 1987 in the
wider class of monoids. As Sakarovitch pointed out, if we restrict
ourselves to groups, the concept is not very interesting, since a
group is a rational monoid if and only if it is finite; however, as
a class of monoids, they are of considerable interest.
We will survey some of the algebraic and computational properties
of, and the relations between, these classes of
monoids. Inparticular, we will present the complete inclusion
structure of these classes of monoids.
Biography:Michael Hoffmann started his studies at the Ruhr-Universitaet-Bochum
in Mathematics and Physics. After four years he went to the
University of Sussex where he was awarded an
MSc in Mathematics. He completed a PhD in Computer Science at the
University of Leicester. After teaching at Loughborough University he
is now a Lecturer in Computer Science in Leicester.
Type: ITEE Seminar
Contact:George Havas, seminar host (havas@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)