The monadic second-order logic of graphs. VII: Graphs as relational structures
type: Item
instance of: scholarly article
title: The monadic second-order logic of graphs. VII: Graphs as relational structures
zbMATH Open document ID: 0809.03006
DOI: 10.1016/0304-3975(92)90148-9
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
review text: [Part VI is reviewed above.] The author defines operations on stuctures that are compatible with monadic second-order logic and that are powerful enough to represent context-free graph and hypergraph grammars of various types, namely, the so-called hyperedge replacement, C-edNCE, and separated handle rewriting grammars. Several results concerning monadic second-order properties of the generated sets are obtained in a uniform way.
reviewed by: Li Xiang
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 64581
zbMATH Keywords: graph grammars
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: hypergraph grammars
zbMATH Keywords: hyperedge replacement
zbMATH Keywords: separated handle rewriting
MaRDI profile type: Publication
full work available at URL: 0304-3975(92)90148-9
OpenAlex ID: W2089928579
cites work: Easy problems for tree-decomposable graphs
cites work: Graph expressions and graph rewritings
cites work: Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
cites work: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
cites work: Q4385531
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
cites work: Q4852905
cites work: Q4037313
cites work: Tree acceptors and some of their applications
cites work: Transformations of structures: An algebraic approach
cites work: Q4037316
cites work: The string generating power of context-free hypergraph grammars
cites work: A comparison of boundary graph grammars and context-free hypergraph grammars
cites work: Hyperedge replacement: grammars and languages
cites work: Q3785988
cites work: Languages that Capture Complexity Classes
cites work: Q4385543
cites work: Q5586299
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
author: Bruno Courcelle
Recommended article: The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
Recommended article: Q3077955
Recommended article: Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
Recommended article: Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
Recommended article: Q4362731
Recommended article: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
Recommended article: The monadic second-order logic of graphs. IV: Definability properties of equational graphs
Recommended article: The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
Recommended article: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
Recommended article: Q2767003
description: scientific article; zbMATH DE number 64581