ITEE seminar: Dr Michael Hoffmann, 10.00AM, Wed 20 Aug 2003

Relationships between different computational classes of monoids.

Speaker: Dr Michael Hoffmann, Department of Computer Science, School of Mathematics and Computer Science, University of Leicester, UK

When: 10.00AM, Wednesday 20 Aug 2003

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.

Contact:

George Havas, seminar host (havas@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator) (guido@itee.uq.edu.au)

ITEE seminar web page: http://www.itee.uq.edu.au/~seminar

[All seminars]