Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
From MaRDI portal
Publication:1919531
DOI10.1016/0168-0072(95)00021-6zbMath0856.03026MaRDI QIDQ1919531
Erich Grädel, Gregory Loren McColm
Publication date: 13 October 1996
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(95)00021-6
infinitary logic; finite structures; hierarchy theorem; transitive closure logic; extensions of Ehrenfeucht-Fraïssé games; prefix classes
Related Items
Dimension Versus Number of Variables, and Connectivity, too, Unnamed Item, Yet another hierarchy theorem, CSP duality and trees of bounded pathwidth, Program schemes, arrays, Lindström quantifiers and zero-one laws
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive power of stratified logic programs
- Parametrization over inductive relations of a bounded number of variables
- Henkin quantifiers and complete problems
- Fixed-point extensions of first-order logic
- The method of forced enumeration for nondeterministic automata
- Number of quantifiers is better than number of tape cells
- Upper and lower bounds for first order expressibility
- Infinitary logics and 0-1 laws
- Elementary induction on abstract structures
- The polynomial-time hierarchy
- Structure and complexity of relational queries
- An application of games to the completeness problem for formalized theories
- Horn clause queries and generalizations
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- Monadic generalized spectra
- On Moschovakis closure ordinals
- Finite partially-ordered quantification
- The diversity of quantifier prefixes