Separating k-separated eNCE graph languages

An eNCE graph grammar is k-separated (k⩾1) if the distance between any two nonterminal nodes in any of its sentential forms is at least k. Let SEP k denote the class of graph languages generated by k-separated grammars. Then, SEP1 (SEP2) is the class of eNCE (boundary eNCE) graph languages, and so SEP2⊊SEP1. Recently, Engelfriet (1991) showed that SEP3⊊SEP2 and conjectured that, in fact, SEP k+1 ⊊SEP k for each k⩾ 1. We prove this conjecture affirmatively.

Authors

• Changwook Kim
• Dong Hoon Lee

Keywords

No keywords are indexed for this paper.