The monadic second-order logic of graphs, II: Infinite graphs of bounded width

DOI10.1007/BF02088013zbMath0694.68043MaRDI QIDQ3470112

Bruno Courcelle

Publication date: 1989

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

decidabilitysecond-order logic of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (05C99)

Related Items

Automatic graphs and D0L-sequences of finite graphs, Regular sets of infinite message sequence charts, Simple monadic theories and partition width, Linearly bounded infinite graphs, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, A logic of reachable patterns in linked data-structures, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Automata-based Representations for Infinite Graphs, An effective version of Stallings' theorem in the case of context-free groups, Automorphism groups of context-free graphs, The monadic second-order logic of graphs. IX: Machines and their behaviours, On the regular structure of prefix rewriting, Unnamed Item, Leaving Traces: A Note on a Sound and Complete Trace Logic for Concurrent Constraint Programs, Logical aspects of Cayley-graphs: the group case, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Deterministic finite automata with recursive calls and DPDAs, \(L(A)=L(B)\)? decidability results from complete formal systems, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, Shelah-Stupp's and Muchnik's iterations revisited

Cites Work

• 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
• The structure of the models of decidable monadic theories of graphs
• Fundamental properties of infinite trees
• The theory of ends, pushdown automata, and second-order logic
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Algebraic semantics
• Infinite hypergraphs. I: Basic properties
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph expressions and graph rewritings
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Initial Algebra Semantics and Continuous Algebras
• Decidability of Second-Order Theories and Automata on Infinite Trees