A comparison of boundary graph grammars and context-free hypergraph grammars (Q918718): Difference between revisions
From MaRDI portal
Latest revision as of 10:23, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A comparison of boundary graph grammars and context-free hypergraph grammars |
scientific article |
Statements
A comparison of boundary graph grammars and context-free hypergraph grammars (English)
0 references
1990
0 references
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.
0 references
graph grammars
0 references
hypergraph grammars
0 references
context-free languages
0 references
0 references