Automata Presenting Structures: A Survey of the Finite String Case

DOI10.2178/bsl/1208442827zbMath1146.03028OpenAlexW2089351755MaRDI QIDQ3503740

Sasha Rubin

Publication date: 9 June 2008

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/bsl/1208442827

zbMATH Keywords

first-order logicfinite automatonmonadic second order logiclogical structuredecidability problem for finite automata and logical structuresfirst order logic of countable many predicatesrecognisability by finite automata and definability by logical formularelationship between definability and recognisabilitystrings and trees over finite alphabet

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Theory of numerations, effectively presented structures (03D45)

Related Items (36)

Tree-automatic scattered linear orders ⋮ Second-order finite automata: expressive power and simple proofs using automatic structures ⋮ Regular Growth Automata: Properties of a Class of Finitely Induced Infinite Machines ⋮ Automatic learners with feedback queries ⋮ Learning pattern languages over groups ⋮ Lamplighter groups and automata ⋮ Automatic models of first order theories ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Clique‐convergence is undecidable for automatic graphs ⋮ Addition machines, automatic functions and open problems of Floyd and Knuth ⋮ String compression in FA-presentable structures ⋮ Deciding the isomorphism problem in classes of unary automatic structures ⋮ Unnamed Item ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ DEL-based epistemic planning: decidability and complexity ⋮ Unnamed Item ⋮ A language hierarchy of binary relations ⋮ Isomorphisms of scattered automatic linear orders ⋮ On automaton presentations of projective planes ⋮ A hierarchy of tree-automatic structures ⋮ Some natural decision problems in automatic graphs ⋮ Automatic learning of subclasses of pattern languages ⋮ Learnability of automatic classes ⋮ Unnamed Item ⋮ The isomorphism relation between tree-automatic structures ⋮ The isomorphism problem for tree-automatic ordinals with addition ⋮ Learners based on transducers ⋮ Analysing Complexity in Classes of Unary Automatic Structures ⋮ Automatic Learners with Feedback Queries ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ Automatic Structures of Bounded Degree Revisited ⋮ Learning Pattern Languages over Groups ⋮ Automatic structures of bounded degree revisited ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ On decidability of list structures ⋮ An example of an automatic graph of intermediate growth

Cites Work

• Unnamed Item
• Unnamed Item
• On direct products of automaton decidable theories
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Finite presentations of infinite structures: Automata and interpretations
• Definability hierarchies of generalized quantifiers
• Automaticity of ordinals and of homogeneous graphs
• Sets recognized by n-tape automata
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata
• LICS 2001 special issue
• Automatic linear orders and trees
• Invariants of Automatic Presentations and Semi-synchronous Transductions
• Logical Reversibility of Computation

This page was built for publication: Automata Presenting Structures: A Survey of the Finite String Case