Abstract
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 SEPk 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{subset of with not equal to}SEP1. Recently, Engelfriet (1991) showed that SEP3{subset of with not equal to}SEP2 and conjectured that, in fact, SEPk+1{subset of with not equal to}SEPk for each k≥ 1. We prove this conjecture affirmatively.
Original language | English |
---|---|
Pages (from-to) | 247-259 |
Number of pages | 13 |
Journal | Theoretical Computer Science |
Volume | 120 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1993 Nov 22 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)