Boundary graph grammars with dynamic edge relabeling

作者:

Highlights:

摘要

Most NLC-like graph grammars generate node-labeled graphs. As one of the exceptions, eNCE graph grammars generate graphs with edge labels as well. We investigate this type of graph grammar and show that the use of edge labels (together with the NCE feature) is responsible for some new properties. Especially boundary eNCE (B-eNCE) grammars are considered. First, although eNCE grammars have the context-sensitive feature of “blocking edges,” we show that B-eNCE grammars do not. Second, we show the existence of a Chomsky normal form and a Greibach normal form for B-eNCE grammars. Third, the boundary eNCE languages are characterized in terms of regular tree and string languages. Fourth, we prove that the class of (boundary) eNCE languages properly contains the closure of the class of (boundary) NLC languages under node relabelings. Analogous results are shown for linear eNCE grammars.

论文关键词:

论文评审过程:Received 21 April 1988, Revised 20 December 1988, Available online 2 December 2003.

论文官网地址:https://doi.org/10.1016/0022-0000(90)90002-3