Monadic second-order logic on tree-like structures

DOI10.1016/S0304-3975(01)00185-2zbMath1026.68087OpenAlexW2067464091MaRDI QIDQ1606130

Igor Walukiewicz

Publication date: 31 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00185-2

zbMATH Keywords

monadic second-order logicdecidabilitytree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (28)

Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints ⋮ Solving Infinite Games in the Baire Space ⋮ Simple monadic theories and partition width ⋮ The mu-calculus and Model Checking ⋮ Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus ⋮ The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic ⋮ Nearest Fixed Points and Concurrent Priority Games ⋮ Solving quantified linear arithmetic by counterexample-guided instantiation ⋮ Contribution of Warsaw logicians to computational logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Model Transformations in Decidability Proofs for Monadic Theories ⋮ On the structure of graphs in the Caucal hierarchy ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ Pushdown module checking ⋮ An Automata-Theoretic Approach to Infinite-State Systems ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ CTL\(^\ast\) with graded path modalities ⋮ Monoidal-closed categories of tree automata ⋮ Unnamed Item ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Regular sets over extended tree structures ⋮ The modalμ-calculus hierarchy over restricted classes of transition systems ⋮ On decidability of list structures ⋮ Shelah-Stupp's and Muchnik's iterations revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An automata theoretic decision procedure for the propositional mu- calculus
• Descriptive set theory
• The monadic theory of order
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Infinite games played on finite graphs
• Monadic second-order definable graph transductions: a survey
• Automata for the modal μ-calculus and related results
• State-strategies for games in F_σδ ∩ G_δσ
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decision methods in the theory of ordinals
• Decidability of Second-Order Theories and Automata on Infinite Trees
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic

This page was built for publication: Monadic second-order logic on tree-like structures