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

DOI10.1007/BF02088013zbMath0694.68043MaRDI QIDQ3470112

No author found.

Publication date: 1989

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

zbMATH Keywords

decidabilitysecond-order logic of graphs

Mathematics Subject Classification ID

Related Items (20)

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

This page was built for publication: The monadic second-order logic of graphs, II: Infinite graphs of bounded width