Capturing MSO with one quantifier

DOI10.1007/978-3-319-23534-9_8MaRDI QIDQ2947170zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar, Luc Segoufin

Publication date 22 September 2015

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

Full work available at URL https://hal.inria.fr/hal-01223378/file/mso-oneQ.pdf

Mathematics Subject Classification ID

Higher-order logic (03B16) Second- and higher-order model theory (03C85)

Recommendations

• Extensions of MSO and the monadic counting hierarchy
• Measure quantifier in monadic second order logic
• Monadic second-order logic on tree-like structures
• Where first-order and monadic second-order logic coincide
• Where first-order and monadic second-order logic coincide

Cites work

• Generalized finite automata theory with an application to a decision problem of second-order logic
• Generalized Quantifiers and Logical Reducibilities
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• scientific article; zbMATH DE number 3941493 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Logics for Unranked Trees: An Overview
• Some Remarks on Generalized Spectra
• Transitive closure logic, nested tree walking automata, and XPath
• Tree acceptors and some of their applications

Cited in

(4)

• Measure quantifier in monadic second order logic
• Computer Science Logic
• First order quantifiers in monadic second order logic
• Extensions of MSO and the monadic counting hierarchy

This page was built for publication: Capturing MSO with one quantifier

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