Undecidability of a weak version of MSO+U

MaRDI QIDQ5216303zbMATH OpenFDO

Authors Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle, A. V. Sreejith

Publication date 17 February 2020

Full work available at URL https://arxiv.org/abs/1807.08506

zbMATH Keywords

\textsc{mso} logicundecidability

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• scientific article; zbMATH DE number 6829362
• On the decidability of MSO+U on infinite trees
• Weak \(\text{MSO}+U\) over infinite trees
• Weak MSO+U with path quantifiers over infinite trees
• On the topological complexity of MSO+U and related automata models

Cites work

• Asymptotic Monadic Second-Order Logic
• Boundedness in languages of infinite words
• Computer Science Logic
• Expressing cardinality quantifiers in monadic second-order logic over chains
• scientific article; zbMATH DE number 6829362 (Why is no real title available?)
• scientific article; zbMATH DE number 1827828 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Infinite and bi-infinite words with decidable monadic theories
• Measure quantifier in monadic second order logic
• On Boolean closed full trios and rational Kripke frames

Cited in

(2)

• scientific article; zbMATH DE number 6829362 (Why is no real title available?)
• On the expansion of monadic second-order logic with Cantor-Bendixson rank and order type predicates

This page was built for publication: Undecidability of a weak version of MSO+U

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