Finite presentations of infinite structures: Automata and interpretations
From MaRDI portal
Publication:1764419
DOI10.1007/s00224-004-1133-yzbMath1061.03038OpenAlexW1966217515MaRDI QIDQ1764419
Achim Blumensath, Erich Grädel
Publication date: 24 February 2005
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-004-1133-y
Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Computable structure theory, computable model theory (03C57)
Related Items
Model-checking CTL* over flat Presburger counter systems ⋮ The isomorphism problem for FST injection structures ⋮ Rewriting Higher-Order Stack Trees ⋮ On the geometry of Cayley automatic groups ⋮ Lamplighter groups and automata ⋮ Processing succinct matrices and vectors ⋮ Rewriting higher-order stack trees ⋮ Regular model checking revisited ⋮ Clique‐convergence is undecidable for automatic graphs ⋮ Unary Automatic Graphs: An Algorithmic Perspective ⋮ Automata Presenting Structures: A Survey of the Finite String Case ⋮ Addition machines, automatic functions and open problems of Floyd and Knuth ⋮ String compression in FA-presentable structures ⋮ Efficient Evaluation of Arbitrary Relational Calculus Queries ⋮ Two Effective Properties of ω-Rational Functions ⋮ Uncountable automatic classes and learning ⋮ The monoid of queue actions ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Automatic presentations and semigroup constructions ⋮ Describing Groups ⋮ Isomorphisms of scattered automatic linear orders ⋮ First-order and counting theories ofω-automatic structures ⋮ A hierarchy of tree-automatic structures ⋮ Some natural decision problems in automatic graphs ⋮ Automatic learning of subclasses of pattern languages ⋮ Learnability of automatic classes ⋮ Model-theoretic properties of \(\omega\)-automatic structures ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Infinite Argumentation Frameworks ⋮ Reachability on prefix-recognizable graphs ⋮ The isomorphism relation between tree-automatic structures ⋮ Ehrenfeucht-Fraïssé goes automatic for real addition ⋮ The isomorphism problem for tree-automatic ordinals with addition ⋮ Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates ⋮ An Automata Theoretic Approach to Rational Tree Relations ⋮ Monitoring Metric First-Order Temporal Properties ⋮ Tree-Automatic Well-Founded Trees ⋮ Analysing Complexity in Classes of Unary Automatic Structures ⋮ Reachability Games on Automatic Graphs ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ The Reachability Problem over Infinite Graphs ⋮ Don't care words with an application to the automata-based approach for real addition ⋮ Uncountable Automatic Classes and Learning ⋮ Automatic presentations for semigroups. ⋮ The isomorphism problem on classes of automatic structures with transitive relations
