The complexity of regular DNLC graph languages

Ijsbrand Jan Aalbersberg; Joost Engelfriet; Grzegorz Rozenberg

doi:10.1016/0022-0000(90)90004-5

The complexity of regular DNLC graph languages

Ijsbrand Jan Aalbersberg
, Joost Engelfriet
, Grzegorz Rozenberg

Research Integrity

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

8 Scopus citations

Abstract

Regular directed node-label controlled graph grammars (RDNLC grammars for short) originated from the need for an elegant mathematical description of dependence graph languages (related to trace languages) and event structure languages (related to Petri nets). In this framework various complexity problems concerning dependence graph languages and event structure languages can be reduced to complexity problems concerning RDNLC languages, i.e., the graph languages generated by RDNLC grammars. It is known that the membership problem for RDNLC languages is NP-complete. This paper investigates various natural restrictions on RDNLC languages and RDNLC grammars and their influence on the complexity of the membership problem. In particular, it is demonstrated that these restrictions lead to logarithmic space recognition algorithms.

Original language	English
Pages (from-to)	376-404
Number of pages	29
Journal	Journal of Computer and System Sciences
Volume	40
Issue number	3
DOIs	https://doi.org/10.1016/0022-0000(90)90004-5
State	Published - Jun 1990

Access to Document

10.1016/0022-0000(90)90004-5

Cite this

@article{0d4e79452037443eaef9b1e6678ba6af,

title = "The complexity of regular DNLC graph languages",

abstract = "Regular directed node-label controlled graph grammars (RDNLC grammars for short) originated from the need for an elegant mathematical description of dependence graph languages (related to trace languages) and event structure languages (related to Petri nets). In this framework various complexity problems concerning dependence graph languages and event structure languages can be reduced to complexity problems concerning RDNLC languages, i.e., the graph languages generated by RDNLC grammars. It is known that the membership problem for RDNLC languages is NP-complete. This paper investigates various natural restrictions on RDNLC languages and RDNLC grammars and their influence on the complexity of the membership problem. In particular, it is demonstrated that these restrictions lead to logarithmic space recognition algorithms.",

author = "\{Jan Aalbersberg\}, Ijsbrand and Joost Engelfriet and Grzegorz Rozenberg",

year = "1990",

month = jun,

doi = "10.1016/0022-0000(90)90004-5",

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

volume = "40",

pages = "376--404",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - The complexity of regular DNLC graph languages

AU - Jan Aalbersberg, Ijsbrand

AU - Engelfriet, Joost

AU - Rozenberg, Grzegorz

PY - 1990/6

Y1 - 1990/6

N2 - Regular directed node-label controlled graph grammars (RDNLC grammars for short) originated from the need for an elegant mathematical description of dependence graph languages (related to trace languages) and event structure languages (related to Petri nets). In this framework various complexity problems concerning dependence graph languages and event structure languages can be reduced to complexity problems concerning RDNLC languages, i.e., the graph languages generated by RDNLC grammars. It is known that the membership problem for RDNLC languages is NP-complete. This paper investigates various natural restrictions on RDNLC languages and RDNLC grammars and their influence on the complexity of the membership problem. In particular, it is demonstrated that these restrictions lead to logarithmic space recognition algorithms.

AB - Regular directed node-label controlled graph grammars (RDNLC grammars for short) originated from the need for an elegant mathematical description of dependence graph languages (related to trace languages) and event structure languages (related to Petri nets). In this framework various complexity problems concerning dependence graph languages and event structure languages can be reduced to complexity problems concerning RDNLC languages, i.e., the graph languages generated by RDNLC grammars. It is known that the membership problem for RDNLC languages is NP-complete. This paper investigates various natural restrictions on RDNLC languages and RDNLC grammars and their influence on the complexity of the membership problem. In particular, it is demonstrated that these restrictions lead to logarithmic space recognition algorithms.

UR - https://www.scopus.com/pages/publications/0025447212

U2 - 10.1016/0022-0000(90)90004-5

DO - 10.1016/0022-0000(90)90004-5

M3 - Artículo

AN - SCOPUS:0025447212

SN - 0022-0000

VL - 40

SP - 376

EP - 404

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

The complexity of regular DNLC graph languages

Abstract

Access to Document

Other files and links

Fingerprint

Cite this