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

DOI10.1093/JIGPAL/9.6.769MaRDI QIDQ3147357zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(4)

• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• The hierarchy theorem for second order generalized quantifiers
• scientific article; zbMATH DE number 7407786 (Why is no real title available?)
• scientific article; zbMATH DE number 1256653 (Why is no real title available?)

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)