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

DOI10.1016/0304-3975(95)00049-3zbMATH Open0872.03026OpenAlexW2020520119MaRDI QIDQ671992FDOQ671992

Authors: 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

Recommendations

• Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
• Graph structure and monadic second-order logic. A language-theoretic approach
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• scientific article; zbMATH DE number 1696755
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs

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)

Cites Work

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

Cited In (14)

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

This page was built for publication: The monadic second-order logic of graphs. IX: Machines and their behaviours

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