Logical Approaches to Computational Barriers

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 classes 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. Finally, we outline some of the basic properties of sequential automatic unary algebras.

websites: Arnold Beckmann | 2008-05-18 |