First order quantifiers in monadic second order logic

DOI10.2178/JSL/1080938831MaRDI QIDQ5311712zbMATH OpenOpenAlexFDO

Authors H. Jerome Keisler, Wafik Boulos Lotfallah

Publication date 29 August 2005

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.596.2619

zbMATH Keywords

expressive powerfirst-order closurefirst-order quantifiermonadic second-order logicquantifier hierarchy

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Descriptive complexity and finite models (68Q19)

Recommendations

• A toolkit for first order extensions of monadic games
• Extensions of MSO and the monadic counting hierarchy
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Capturing MSO with one quantifier
• Relativized logspace and generalized quantifiers over finite ordered structures

Cites work

• Descriptive complexity
• Monadic generalized spectra
• Reachability is harder for directed than for undirected finite graphs
• The diversity of quantifier prefixes

Cited in

(9)

• Logical laws for existential monadic second-order sentences with infinite first-order parts
• On the first-order prefix hierarchy
• On second-order monadic monoidal and groupoidal quantifiers
• On an interpretation of second order quantification in first order intuitionistic propositional logic
• One quantifier will do in existential monadic second-order logic over pictures
• Monadic Second Order Logic with Measure and Category Quantifiers
• \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
• Quantitative Monadic Second-Order Logic
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication: First order quantifiers in monadic second order logic

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