Language - generating Power of HRNCE Grammars


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 3, No. 7, pp. 1659-1668, Dec. 1996
10.3745/KIPSTE.1996.3.7.1659,   PDF Download:

Abstract

Graph grammars generate graph languages while string grammars generate string languages which are the subset of graph languages. One of the most successful graph grammars models is the NLC grammars. which generate graphs by replacing a node by a graph through node labels. For grammars generating hypergraphs which are the superset of graph, there are CFHG grammars, which replace a hyperedge by a hypergraph through their preidentified gluing points, an extension of CFGH grammars called HH grammars, which replace a handle by a hypergraph through the rewriting mechanism that can also duplicate of delete the hyperedges surrounding the replaced handle, and finally HRNCE grammars, which replace a handle by a hypergraph through an eNCE way of rewriting. In this paper, we compare the language-generating power of HRNCE grammars with that of graph grammars mentioned above by comparing graph languages generated by them, respectively.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. T. Eui and P. D. Sun, "Language - generating Power of HRNCE Grammars," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 3, no. 7, pp. 1659-1668, 1996. DOI: 10.3745/KIPSTE.1996.3.7.1659.

[ACM Style]
Jeong Tae Eui and Park Dong Sun. 1996. Language - generating Power of HRNCE Grammars. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 3, 7, (1996), 1659-1668. DOI: 10.3745/KIPSTE.1996.3.7.1659.