**
**

**Huschenbett, Martin, Kartzow, Alexander and Schlicht, Philipp (2017): Pumping for ordinal-automatic structures. In: Computability-the Journal of the Association Cie, Vol. 6, No. 2: pp. 125-164**

**Full text not available from 'Open Access LMU'.**

## Abstract

An alpha-automaton (for alpha some ordinal) is an automaton similar to a Muller automaton that processes words of length alpha. A structure is called alpha-automatic if it can be presented by alpha-automata (completely analogous to the notion of automatic structures which can be presented by the well-known finite automata). We call a structure ordinal-automatic if it is alpha-automatic for some ordinal alpha. We continue the study of ordinal-automatic structures initiated by Schlicht and Stephan as well as by Finkel and Todorcevic. We develop a pumping lemma for alpha-automata (processing finite alpha-words, i.e., words of length alpha that have one fixed letter at all but finitely many positions). Using this pumping, we provide counterparts for the class of ordinal-automatic structures to several results on automatic structures: Every finite word alpha-automatic structure has an injective finite word alpha-automatic presentation for all alpha < omega(1) + omega(omega). This bound is sharp. We classify completely the finite word omega(n)-automatic Boolean algebras. Moreover, we show that the countable atomless Boolean algebra does not have an injective finite-word ordinal-automatic presentation. We separate the class of finite-word ordinal-automatic structures from that of tree-automatic structures by showing that free term algebras with at least 2 generators (and one binary function) are not ordinal-automatic while the free term algebra with countable infinitely many generators is known to be tree-automatic. For every ordinal alpha < omega(1) + omega(omega), we provide a sharp bound on the height of the finite word alpha-automatic well-founded order forests. For every ordinal alpha < omega(1)+ omega(omega), we provide a structure (sic)(alpha) that is complete for the class of finite-word alpha-automatic structures with respect to first-order interpretations. As a byproduct, we also lift Schlicht and Stephans's characterisation of the injectively finite-word alpha-automatic ordinals to the noninjective setting.

Item Type: | Journal article |
---|---|

Faculties: | Mathematics, Computer Science and Statistics > Computer Science |

Subjects: | 000 Computer science, information and general works > 004 Data processing computer science |

ISSN: | 2211-3568 |

Language: | English |

Item ID: | 55638 |

Date Deposited: | 14. Jun 2018 09:59 |

Last Modified: | 04. Nov 2020 13:35 |