Three lectures on automatic structures

MaRDI QIDQ3079695zbMATH OpenFDO

Authors Bakhadyr Khoussainov, Mia Minnes

Publication date 2 March 2011

Full work available at URL https://arxiv.org/abs/0809.3430

zbMATH Keywords

Borel structureBüchi automatic structurecomputable structuresRabin automatic structuretree automatic structure

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15)

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.

Recommendations

• Automatic Structures: Richness and Limitations
• Finite presentations of infinite structures: Automata and interpretations
• Theories of Automatic Structures and Their Complexity
• scientific article; zbMATH DE number 2040323
• Automatic structures: twenty years later

Cited in

(29)

• Learning pattern languages over groups
• From automatic structures to automatic groups.
• Searching for applicable versions of computable structures
• Lamplighter groups and automata
• Effective categoricity of automatic equivalence and nested equivalence structures
• Online presentations of finitely generated structures
• Automatic structures
• The isomorphism problem for tree-automatic ordinals with addition
• On the width of regular classes of finite structures
• On decidability of list structures
• Deciding the isomorphism problem in classes of unary automatic structures
• Tree-automatic scattered linear orders
• A computation model with automatic functions and relations as primitive operations
• String compression in FA-presentable structures
• Cayley automatic groups and numerical characteristics of Turing transducers
• Learning pattern languages over groups
• Automata on Ordinals and Linear Orders
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• Analysing Complexity in Classes of Unary Automatic Structures
• On automaton presentations of projective planes
• Climbing up the elementary complexity classes with theories of automatic structures
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Learners based on transducers
• Addition machines, automatic functions and open problems of Floyd and Knuth
• Alternating automatic register machines
• Decidability for Sturmian words
• Quasi-isometric reductions between infinite strings
• Automatic learning of subclasses of pattern languages
• Automatic structures and the problem of natural well-orderings

This page was built for publication: Three lectures on automatic structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3079695)