The monadic second-order logic of graphs. VII: Graphs as relational structures

DOI10.1016/0304-3975(92)90148-9zbMath0809.03006OpenAlexW2089928579MaRDI QIDQ1193407

Bruno Courcelle

Publication date: 27 September 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90148-9

zbMATH Keywords

monadic second-order logicgraph grammarshyperedge replacementhypergraph grammarsseparated handle rewriting

Mathematics Subject Classification ID

Related Items (24)

Monadic second-order definable graph transductions: a survey ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Simple monadic theories and partition width ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Recognizable sets of graphs: equivalent definitions and closure properties ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Logical description of context-free graph languages ⋮ Farrell polynomials on graphs of bounded tree width ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Upper bounds to the clique width of graphs ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ Recognizability, hypergraph operations, and logical types ⋮ A model-theoretic characterisation of clique width ⋮ Relational structures constructible by quantifier free definable operations ⋮ Unnamed Item ⋮ Nondeterministic operations on finite relational structures ⋮ Graph operations characterizing rank-width ⋮ The recognizability of sets of graphs is a robust property ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ The evaluation of first-order substitution is monadic second-order compatible ⋮ Shelah-Stupp's and Muchnik's iterations revisited ⋮ An operational and denotational approach to non-context-freeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• A comparison of boundary graph grammars and context-free hypergraph grammars
• 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
• The string generating power of context-free hypergraph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Languages that Capture Complexity Classes
• Graph expressions and graph rewritings
• Transformations of structures: An algebraic approach
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: The monadic second-order logic of graphs. VII: Graphs as relational structures