One quantifier will do in existential monadic second-order logic over pictures

DOI10.1007/BFB0055826MaRDI QIDQ4218153zbMATH OpenFDO

Authors Oliver Matz

Publication date 11 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0055826

zbMATH Keywords

existential fragmentmonadic second-order logic over picture modelsquantifier alternation hierarchyword models

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Formal languages and automata (68Q45)

Recommendations

• The monadic quantifier alternation hierarchy over grids and pictures
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Expressive power of monadic logics on words, trees, pictures, and graphs
• First order quantifiers in monadic second order logic

Cited in

(5)

• Arity and alternation: a proper hierarchy in higher order logics
• The monadic quantifier alternation hierarchy over grids and graphs
• A logical approach to locality in pictures languages
• Recognizable vs. Regular Picture Languages
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication: One quantifier will do in existential monadic second-order logic over pictures

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