Expressive equivalence of least and inflationary fixed-point logic

DOI10.1016/j.apal.2004.02.001zbMath1052.03012OpenAlexW1983330347MaRDI QIDQ1886320

Stephan Kreutzer

Publication date: 18 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.02.001

zbMATH Keywords

expressive powerfinite structuresfixed-point logicIFP-nesting depth hierarchyinfinite structuresLFP-alternation hierarchy

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of model theory (03C98)

Related Items (5)

Symbioses between mathematical logic and computer science ⋮ FO(ID) as an extension of DL with rules ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Logic and Game Theory ⋮ Canonisation and Definability for Graphs of Bounded Rank Width

Cites Work

• Unnamed Item
• Fixed-point extensions of first-order logic
• Elementary induction on abstract structures
• Relational queries computable in polynomial time
• On nonmonotone inductive definability
• On monotone vs. nonmonotone induction
• Fixed Point Logics

This page was built for publication: Expressive equivalence of least and inflationary fixed-point logic