First-order and counting theories ofω-automatic structures
From MaRDI portal
Publication:5387304
DOI10.2178/jsl/1208358745zbMath1141.03015OpenAlexW2569340810MaRDI QIDQ5387304
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
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 (14)
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
- 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
This page was built for publication: First-order and counting theories ofω-automatic structures
