The monadic second-order logic of graphs. IX: Machines and their behaviours

DOI10.1016/0304-3975(95)00049-3zbMath0872.03026OpenAlexW2020520119MaRDI QIDQ671992

Bruno Courcelle

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00049-3

zbMATH Keywords

program verificationdynamic properties of machinesmonadic second-order property of the behaviour of a machinemonadic theory of an algebraic treestatic properties

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Related Items

Simple monadic theories and partition width, On deeply critical oriented cliques, Unfoldings and Coverings of Weighted Graphs, A Hierarchy of Automaticω-Words having a Decidable MSO Theory, Model Transformations in Decidability Proofs for Monadic Theories, Unnamed Item, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, Computer science and the fine structure of Borel sets, Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence, Regular sets over extended tree structures, Monadic second-order logic, graph coverings and unfoldings of transition systems, A logic-based approach to incremental reasoning on multi-agent systems, The evaluation of first-order substitution is monadic second-order compatible

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• Fundamental properties of infinite trees
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• A representation of trees by languages. II
• Corrigendum to ``DPDA's in ``atomic normal form and applications to equivalence problems
• Monadic second-order definable graph transductions: a survey
• CTL\(^*\) and ECTL\(^*\) as fragments of the modal \(\mu\)-calculus
• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Algebraic automata and context-free sets