Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Sequential Automatic Algebras

Author(s): Bakhadyr Khoussainov, Michael Brough and Peter Nelson
Slot: Array, 11:40-12:00, col. 4


An {\em automatic sequential algebra} is a structure of the type
$(A; f_1,\ldots, f_n)$, where $A$ is recognised by a finite automaton, and
functions $f_1, \ldots, f_n$ are total operations  on $A$ that are computed
by input-output automata. Our input-output automata are variations of Mealy
automata.  We study some of the fundamental properties of these algebras
and provide many examples. We give classification results  for certain the
of groups, Boolean algebras, and linear orders. We also introduce different
classes of sequential automatic algebras and give separating examples. We  
investigate linear orders considered as sequentially automatic algebras.
we outline some of  the basic properties of sequential automatic unary algebras.

websites: Arnold Beckmann 2008-05-18