Separating k-separated eNCE graph languages

Changwook Kim; Dong Hoon Lee

doi:10.1016/0304-3975(93)90290-A

Separating k-separated eNCE graph languages

Changwook Kim, Dong Hoon Lee

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

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 SEP_k denote the class of graph languages generated by k-separated grammars. Then, SEP₁ (SEP₂) is the class of eNCE (boundary eNCE) graph languages, and so SEP₂{subset of with not equal to}SEP₁. Recently, Engelfriet (1991) showed that SEP₃{subset of with not equal to}SEP₂ and conjectured that, in fact, SEP_k+1{subset of with not equal to}SEP_k 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	https://doi.org/10.1016/0304-3975(93)90290-A
Publication status	Published - 1993 Nov 22
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/0304-3975(93)90290-A

Cite this

@article{007234be56dd4979a5a5b50ef0dfb23a,

title = "Separating k-separated eNCE graph languages",

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.",

author = "Changwook Kim and Lee, {Dong Hoon}",

year = "1993",

month = nov,

day = "22",

doi = "10.1016/0304-3975(93)90290-A",

language = "English",

volume = "120",

pages = "247--259",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Separating k-separated eNCE graph languages

AU - Kim, Changwook

AU - Lee, Dong Hoon

PY - 1993/11/22

Y1 - 1993/11/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027694160&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(93)90290-A

DO - 10.1016/0304-3975(93)90290-A

M3 - Article

AN - SCOPUS:0027694160

SN - 0304-3975

VL - 120

SP - 247

EP - 259

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -

Separating k-separated eNCE graph languages

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this