First-order and counting theories ofω-automatic structures

DOI10.2178/jsl/1208358745zbMath1141.03015MaRDI 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

decidability; generalized quantifiers; \(\omega\)-automatic structures

Mathematics Subject Classification ID

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

03C80: Logic with extra quantifiers and operators

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item