Three Lectures on Automatic Structures

Abstract

This paper grew out of three tutorial lectures on automatic structures given by the first author at the Logic Colloquium 2007. We discuss variants of automatic structures related to several models of computation: word automata, tree automata, Buchi automata, and Rabin automata. Word automata process finite strings, tree automata process finite labeled trees, Buchi automata process infinite strings, and Rabin automata process infinite binary labeled trees. Automatic structures are mathematical objects which can be represented by (word, tree, Buchi, or Rabin) automata. The study of properties of automatic structures is a relatively new and very active area of research.

43 pages, based on tutorial lectures at Logic Colloquium 2007

Cited by in corpus (8)

• Decidability for Sturmian words
• Measuring closeness between Cayley automatic groups and automatic groups
• The additive group of the rationals does not have an automatic presentation
• String Compression in FA-Presentable Structures
• Alternating Automatic Register Machines
• On the Width of Regular Classes of Finite Structures
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• Towards quantitative classification of Cayley automatic groups