Hierarchies in transitive closure logic, stratified Datalog and infinitary logic

DOI10.1016/0168-0072(95)00021-6zbMath0856.03026OpenAlexW2073314176MaRDI 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

zbMATH Keywords

infinitary logicfinite structureshierarchy theoremtransitive closure logicextensions of Ehrenfeucht-Fraïssé gamesprefix classes

Mathematics Subject Classification ID

Database theory (68P15) Model theory of finite structures (03C13) Other infinitary logic (03C75)

Related Items

Dimension Versus Number of Variables, and Connectivity, too, CSP duality and trees of bounded pathwidth, Unnamed Item, Yet another hierarchy theorem, Program schemes, arrays, Lindström quantifiers and zero-one laws

Uses Software

• Datalog
• GraphLog

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