Hierarchies in transitive closure logic, stratified Datalog and infinitary logic

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

zbMATH Keywords

infinitary logic; finite structures; hierarchy theorem; transitive closure logic; extensions of Ehrenfeucht-Fraïssé games; prefix classes

Mathematics Subject Classification ID

68P15: Database theory

03C13: Model theory of finite structures

03C75: Other infinitary logic

Related Items

Dimension Versus Number of Variables, and Connectivity, too, Yet another hierarchy theorem, CSP duality and trees of bounded pathwidth, 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