New algorithm for weak monadic second-order logic on inductive structures

DOI10.1007/978-3-642-15205-4_29MaRDI QIDQ3586053zbMATH OpenOpenAlexFDO

Authors Tobias Ganzow, Łukasz Kaiser

Publication date 3 September 2010

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL http://publications.rwth-aachen.de/record/119907

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Weak \(\text{MSO}+U\) over infinite trees
• The Monadic Theory of Tree-like Structures
• Weak MSO+U with path quantifiers over infinite trees
• The complexity of first-order and monadic second-order logic revisited
• Monadic second order finite satisfiability and unbounded tree-width

Cited in

(11)

• A unification algorithm for second-order monadic terms
• A weakly monotonic backward induction algorithm on finite bounded subsets of vector lattices.
• Nested antichains for WS1S
• Lazy automata techniques for WS1S
• Recursion schemes and the WMSO+U logic
• Courcelle's theorem -- a game-theoretic approach
• Recursion schemes, the MSO logic, and the \textsf{U} quantifier
• scientific article; zbMATH DE number 3321243 (Why is no real title available?)
• Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure
• Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure
• Antiprenexing for WSkS: a little goes a long way

This page was built for publication: New algorithm for weak monadic second-order logic on inductive structures

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