Existential Fixed-Point Logic as a Fragment of Second-Order Logic

DOI10.1007/978-3-319-23534-9_3zbMath1465.03074OpenAlexW2295418520MaRDI QIDQ2947165

Andreas Blass

Publication date: 22 September 2015

Published in: Fields of Logic and Computation II (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-23534-9_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Logic with extra quantifiers and operators (03C80) Higher-order logic (03B16)

Cites Work

• Unnamed Item
• Unnamed Item
• Capturing complexity classes by fragments of second-order logic
• Elementary induction on abstract structures
• Existential Fixed-Point Logic, Universal Quantifiers, and Topoi