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

computable structuresBorel structuretree automatic structureBüchi automatic structureRabin automatic structure

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) 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)

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

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)