A comparison of boundary graph grammars and context-free hypergraph grammars
type: Item
instance of: scholarly article
title: A comparison of boundary graph grammars and context-free hypergraph grammars
zbMATH Open document ID: 0706.68067
DOI: 10.1016/0890-5401(90)90038-J
author: Joost Engelfriet
author: Grzegorz Rozenberg
published in: Information and Computation
publication date: 1990-01-01T00:00:00Z
review text: The purpose of this paper is to compare the (language) generative power of context-free hypergraph grammars (CFHG) and boundary graph grammars (B-edNCE). These generative mechanisms are different in nature: edge placing versus node placing and, much more, directed hypergraphs generators versus graph generators. Some technical results are thus in order: normal forms for B-edNCE, some closure properties of B-edNCE and, of course, a definition of hypergraphs representations as graphs (and vice-versa). CFHG and B-edNCE (of bounded nonterminal degree) are shown to have the same power (as graphs, and also as hypergraphs generators). Arbitrary B-edNCE have the same hypergraph generative power as the CFHG, but, as graph generators, their power strictly increases. The paper is almost self-contained, partly because of the lack of widely accepted definitions for the studied classes of grammars.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4160145
zbMATH Keywords: graph grammars
zbMATH Keywords: hypergraph grammars
zbMATH Keywords: context-free languages
reviewed by: Cristian Masalagiu
MaRDI profile type: Publication
cites work: Translations on a context free grammar
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Graph expressions and graph rewritings
cites work: Q3785989
cites work: Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
cites work: A taxonomy of problems with fast parallel algorithms
cites work: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
cites work: Q3785986
cites work: Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
cites work: Q1839237
cites work: Q3779767
cites work: Complexity of boundary graph languages
cites work: Linear graph grammars: Power and complexity
cites work: Apex graph grammars and attribute grammars
cites work: Boundary graph grammars with dynamic edge relabeling
cites work: Tree transducers, L systems, and two-way machines
cites work: Q3774975
cites work: On the structure of node-label-controlled graph languages
cites work: Graph grammars with neighbourhood-controlled embedding
cites work: On sequential and parallel node-rewriting graph grammars
cites work: The NP-completeness column: an ongoing guide
cites work: Q3714485
cites work: Q3795250
cites work: Q3786030
cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
cites work: Graph theoretic closure properties of the family of boundary NLC graph languages
cites work: Combinatorial properties of boundary NLC graph languages
cites work: Q3714483
cites work: Q3785991
Recommended article: The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
Recommended article: Contextual Hypergraph Grammars – A New Approach to the Generation of Hypergraph Languages
Recommended article: Q4284239
Recommended article: Q3219131
Recommended article: Q3339312
Recommended article: Context-free hypergraph grammars with node rewriting
Recommended article: Q4033498
Recommended article: Q3785991
Recommended article: Complexity of boundary graph languages
Recommended article: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
description: scientific article; zbMATH DE number 4160145