The complexity of regular DNLC graph languages

摘要

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.