First-order and counting theories ofω-automatic structures

DOI10.2178/jsl/1208358745zbMath1141.03015OpenAlexW2569340810MaRDI QIDQ5387304

Markus Lohrey, Dietrich Kuske

Publication date: 8 May 2008

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

Full work available at URL: https://projecteuclid.org/euclid.jsl/1208358745

zbMATH Keywords

decidabilitygeneralized quantifiers\(\omega\)-automatic structures

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Logic with extra quantifiers and operators (03C80)

Related Items

An optimal construction of Hanf sentences ⋮ Two Effective Properties of ω-Rational Functions ⋮ A hierarchy of tree-automatic structures ⋮ Expressing cardinality quantifiers in monadic second-order logic over chains ⋮ Model-theoretic properties of \(\omega\)-automatic structures ⋮ Reachability on prefix-recognizable graphs ⋮ The isomorphism relation between tree-automatic structures ⋮ From automatic structures to automatic groups. ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ Cardinality Quantifiers in MLO over Trees ⋮ Automatic Structures of Bounded Degree Revisited ⋮ Automatic structures of bounded degree revisited ⋮ Counting problems for parikh images ⋮ Some problems in automata theory which depend on the models of set theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinity problems and countability problems for \(\omega \)-automata
• A uniform method for proving lower bounds on the computational complexity of logical theories
• On direct products of automaton decidable theories
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Finite presentations of infinite structures: Automata and interpretations
• Weak Second‐Order Arithmetic and Finite Automata
• Definable relations and first-order query languages over strings
• A local normal form theorem for infinitary logic with unary quantifiers