Thin MSO with a probabilistic path quantifier

DOI10.4230/LIPICS.ICALP.2016.96MaRDI QIDQ4598237zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2016.96

zbMATH Keywords

automatainfinite treesMSOprobabilistic temporal logics

Mathematics Subject Classification ID

Probability and inductive logic (03B48) Automata and formal grammars in connection with logical questions (03D05) Temporal logic (03B44)

Recommendations

• Probabilistic regular expressions and MSO logic on finite trees
• Weak MSO+U with path quantifiers over infinite trees
• Measure quantifier in monadic second order logic
• Weak \(\text{MSO}+U\) over infinite trees
• Baire category quantifier in monadic second order logic

Cited in

(6)

• MSO+\( \nabla \) is undecidable
• Probabilistic regular expressions and MSO logic on finite trees
• Alternating nonzero automata
• Weak MSO+U with path quantifiers over infinite trees
• Measure quantifier in monadic second order logic
• Baire category quantifier in monadic second order logic

This page was built for publication: Thin MSO with a probabilistic path quantifier

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