On the membership problem for regular DNLC grammars

IJ J. Aalbersberg; G. Rozenberg; A. Ehrenfeucht

doi:10.1016/0166-218X(86)90070-3

On the membership problem for regular DNLC grammars

IJ J. Aalbersberg, G. Rozenberg, A. Ehrenfeucht

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

23 Scopus citations

Abstract

There are (at least) three motivations to study the class of regular directed node-label controlled graph grammars (regular DNLC grammars for shor): (1) it fits very well into the hierarchy of subclasses of DNLC grammars, (2) it generalizes naturally right-linear string grammars and (3) it provides a useful framework for the theory of concurrent systems based on the theory of traces. The complexity of (the membership problem for) the class of regular DNLC grammars is investigated.

Original language	English
Pages (from-to)	79-85
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	13
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(86)90070-3
State	Published - Jan 1986
Externally published	Yes

Access to Document

10.1016/0166-218X(86)90070-3

Cite this

@article{729096e3045245d2b9b4dceb10e5ab26,

title = "On the membership problem for regular DNLC grammars",

abstract = "There are (at least) three motivations to study the class of regular directed node-label controlled graph grammars (regular DNLC grammars for shor): (1) it fits very well into the hierarchy of subclasses of DNLC grammars, (2) it generalizes naturally right-linear string grammars and (3) it provides a useful framework for the theory of concurrent systems based on the theory of traces. The complexity of (the membership problem for) the class of regular DNLC grammars is investigated.",

author = "Aalbersberg, {IJ J.} and G. Rozenberg and A. Ehrenfeucht",

year = "1986",

month = jan,

doi = "10.1016/0166-218X(86)90070-3",

language = "Ingl{\'e}s",

volume = "13",

pages = "79--85",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - On the membership problem for regular DNLC grammars

AU - Aalbersberg, IJ J.

AU - Rozenberg, G.

AU - Ehrenfeucht, A.

PY - 1986/1

Y1 - 1986/1

N2 - There are (at least) three motivations to study the class of regular directed node-label controlled graph grammars (regular DNLC grammars for shor): (1) it fits very well into the hierarchy of subclasses of DNLC grammars, (2) it generalizes naturally right-linear string grammars and (3) it provides a useful framework for the theory of concurrent systems based on the theory of traces. The complexity of (the membership problem for) the class of regular DNLC grammars is investigated.

AB - There are (at least) three motivations to study the class of regular directed node-label controlled graph grammars (regular DNLC grammars for shor): (1) it fits very well into the hierarchy of subclasses of DNLC grammars, (2) it generalizes naturally right-linear string grammars and (3) it provides a useful framework for the theory of concurrent systems based on the theory of traces. The complexity of (the membership problem for) the class of regular DNLC grammars is investigated.

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

U2 - 10.1016/0166-218X(86)90070-3

DO - 10.1016/0166-218X(86)90070-3

M3 - Artículo

AN - SCOPUS:0022503511

SN - 0166-218X

VL - 13

SP - 79

EP - 85

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

On the membership problem for regular DNLC grammars

Abstract

Access to Document

Other files and links

Fingerprint

Cite this