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 - http://www.scopus.com/inward/record.url?scp=0025447212&partnerID=8YFLogxK
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 -