Nonterminal separation in graph grammars
The eNLCE model of graph grammars was introduced as a variation of the successful NLC model. In a NLC grammar the left hand side of a production is a single labeled node, the right hand side is a node labeled graph and the embedding mechanism depends solely on the labels of the nodes involved. In the case of eNCE grammars the embedding mechanism makes use of the identity (rather than the label) of the nodes in the right-hand side of the productions, the generated graphs have also edge labels, the embedding mechanism also uses the labels of the edges incident with the replaced node. In a previous paper the authors have shown that eNCE grammars are more powerful than NLC grammars. It also shown that boundary eNCE grammars (such that there are no edges between nonterminal nodes in any sentential form or, in other words, such that the distance between nonterminals is at least two) are confluent (namely, if two nodes in a graph can be replaced they can be replaced in any order). The present paper investigates the general notion of distance between nonterminal nodes in eNCE grammars. An eNCE grammar is called k- separated, for \(k\geq 1\), if the distance between any two nonterminal nodes in its sentential forms is \(\geq k\). Having previously shown that 1- separated grammars are more powerful than 2-separated grammars, the authors prove that 2-separated grammars are more powerful than 3- separated grammars and conjecture that, for \(k\geq 3\), k-separated grammars are more powerful than \((k+1)\)-separated grammars. Another considered restriction on graph grammars is an apex restriction. An eNCE grammar is an apex eNCE grammar if the embedding mechanism can only establish edges between terminal nodes. For apex grammars to be k- separated has no influence on the generating power, namely it is shown that each apex language can be generated by a k-separated apex grammar.
- A comparison of boundary graph grammars and context-free hypergraph grammars
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Apex graph grammars and attribute grammars
- Boundary graph grammars with dynamic edge relabeling
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Combinatorial properties of boundary NLC graph languages
- Complexity of boundary graph languages
- Graph grammars with neighbourhood-controlled embedding
- Graph theoretic closure properties of the family of boundary NLC graph languages
- Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
- Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
- scientific article; zbMATH DE number 3943061 (Why is no real title available?)
- scientific article; zbMATH DE number 4049100 (Why is no real title available?)
- scientific article; zbMATH DE number 4049101 (Why is no real title available?)
- scientific article; zbMATH DE number 4049105 (Why is no real title available?)
- Linear graph grammars: Power and complexity
- On generators and generative capacity of EOL forms
- On the structure of node-label-controlled graph languages
- Position-restricted grammar forms and grammars
- Restrictions, extensions, and variations of NLC grammars
- Syntactic Analysis and Operator Precedence
- String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
- Separating \(k\)-separated eNCE graph languages
- Hypergraph languages of bounded degree
- Context-free graph languages of bounded degree are generated by apex graph grammars
- HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
- Node replacement graph grammars with dynamic node relabeling
- Handle-rewriting hypergraph grammars
- Bounding the Maximal Parsing Performance of Non-Terminally Separated Grammars
- scientific article; zbMATH DE number 4049105 (Why is no real title available?)
- scientific article; zbMATH DE number 4064512 (Why is no real title available?)
- On the structure of linear apex NLC graph grammars
- A Greibach normal form for context-free graph grammars
- Separation results for separated apex NLC and NCE graph languages
This page was built for publication: Nonterminal separation in graph grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804300)
