Arity hierarchies

DOI10.1016/0168-0072(95)00072-0zbMath0860.03033OpenAlexW4213231691MaRDI QIDQ2563982

Martin Grohe

Publication date: 21 April 1997

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)00072-0

zbMATH Keywords

finite structuresDATALOGextensions of first-order logictransitive closure logicarity hierarchysimultaneous partial fixed-point logicstrictness of hierarchies

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Other model constructions (03C30)

Related Items

Arity and alternation: a proper hierarchy in higher order logics ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Unnamed Item ⋮ Extending partial isomorphisms for the small index property of many \(\omega\)-categorical structures ⋮ Yet another hierarchy theorem ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Fixed-point extensions of first-order logic
• Datalog extensions for database queries and updates
• Extending partial isomorphisms of graphs
• A restricted second order logic for finite structures
• Logical hierarchies in PTIME
• Structure and complexity of relational queries
• Extending partial isomorphisms on finite structures
• A double arity hierarchy theorem for transitive closure logic
• Graph Theory and Probability
• Horn clause queries and generalizations
• Languages that Capture Complexity Classes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item