On infinite transition graphs having a decidable monadic theory

DOI10.1016/S0304-3975(01)00089-5zbMath1019.68066MaRDI QIDQ1853615

Didier Caucal

Publication date: 21 January 2003

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (20)

Model-checking CTL* over flat Presburger counter systems ⋮ Linearly bounded infinite graphs ⋮ Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus ⋮ Properties and limits of recognition of sets of integers by countable automata ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Unnamed Item ⋮ On complexity functions of infinite words associated with generalized Dyck languages ⋮ Verification of qualitative \(\mathbb Z\) constraints ⋮ Rabin's theorem in the concurrency setting: a conjecture ⋮ On first-order logic and CPDA graphs ⋮ An Automata-Theoretic Approach to Infinite-State Systems ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Reachability on prefix-recognizable graphs ⋮ Families of automata characterizing context-sensitive languages ⋮ Epsilon-reducible context-free languages and characterizations of indexed languages ⋮ ALGEBRAIC LINEAR ORDERINGS ⋮ On the complexity of a family of \(k\)-context-free sequences ⋮ Regular sets over extended tree structures ⋮ Deciding regular grammar logics with converse through first-order logic ⋮ Shelah-Stupp's and Muchnik's iterations revisited

Cites Work

• The theory of ends, pushdown automata, and second-order logic
• The monadic theory of order
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Monadic second-order definable graph transductions: a survey
• Regular canonical systems
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On infinite transition graphs having a decidable monadic theory