On a hierarchy involving transitive closure logic and existential second-order quantification

DOI10.1093/JIGPAL/9.6.769zbMATH Open1001.03036OpenAlexW2103196177MaRDI QIDQ3147357FDOQ3147357

Authors: Iain Stewart, Richard L. Gault 

Publication date: 21 October 2002

Published in: Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/jigpal/9.6.769

Recommendations

• A double arity hierarchy theorem for transitive closure logic
• Arity and alternation: a proper hierarchy in higher order logics
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Arity hierarchies
• Foundations of Information and Knowledge Systems

zbMATH Keywords

finite model theorymonadic second-order logicdescriptive complexitytransitive closure logicEhrenfeucht-Fraïssé game

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Cited In (4)

• The hierarchy theorem for second order generalized quantifiers
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On a hierarchy involving transitive closure logic and existential second-order quantification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3147357)