The complexity of regular DNLC graph languages. (English) Zbl 0694.68045

Summary: 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.


68Q45 Formal languages and automata
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aalbersberg, Ij. J.; Engelfriet, J.; Rozenberg, G., The Complexity of Regular DNLC Graph Grammars, (Technical Rept. 86-03 (1986), University of Leiden) · Zbl 0694.68045
[2] Aalbersberg, Ij. J.; Engelfriet, J.; Rozenberg, G., Restricting the complexity of regular DNLC languages, (Proceedings, 3rd Internat. Workshop on Graph-Grammars and Their Application to Computer Science. Proceedings, 3rd Internat. Workshop on Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 291 (1987), Springer-Verlag: Springer-Verlag New York/Berlin), 147-166 · Zbl 0643.68111
[3] Aalbersberg, Ij. J.; Ehrenfeucht, A.; Rozenberg, G., On the membership problem of regular DNLC grammars, Discrete Appl. Math., 13, 79-85 (1986) · Zbl 0602.68064
[4] Aalbersberg, Ij. J.; Rozenberg, G., Traces, dependency graphs and DNLC grammars, Discrete Appl. Math., 11, 299-306 (1985) · Zbl 0601.68045
[5] Aalbersberg, Ij. J.; Rozenberg, G., Theory of traces, Theoret. Comput. Sci., 60, 1-82 (1988) · Zbl 0652.68017
[6] Brandenburg, F. J., On polynomial time graph grammars, (Proceedings, STACS ’88. Proceedings, STACS ’88, Lecture Notes in Computer Science, Vol. 294 (1988), Springer-Verlag: Springer-Verlag New York/Berlin), 227-236 · Zbl 0644.68097
[7] Cook, S. A., Characterizations of pushdown machines in terms of time-bounded computers, J. Assoc. Comput. Mach., 18, 4-18 (1971) · Zbl 0222.02035
[8] Engelfriet, J.; Leih, G., Linear Graph Grammars: Power and Complexity, Inform. and Comput., 81, 88-121 (1989) · Zbl 0684.68088
[9] Engelfriet, J.; Leih, G., Complexity of Boundary Graph Languages, (Technical Rept. 88-07 (1988), University of Leiden), RAIRO Tutor. Inform, Appl., in press · Zbl 0701.68062
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability-A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[11] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[12] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[13] Immermann, N., Nondeterministic space is closed under complement, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[14] Janssens, D.; Rozenberg, G., A characterization of context-free string languages by directed node-label controlled graph grammars, Acta Inform., 16, 63-85 (1981) · Zbl 0464.68077
[15] Lange, K.-J.; Welzl, E., String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing, Discrete Appl. Math., 16, 17-30 (1987) · Zbl 0619.68064
[16] Lautemann, C., Efficient algorithms on context-free graph languages, (Proceedings, 15th ICALP. Proceedings, 15th ICALP, Lecture Notes in Computer Science, Vol. 317 (1988), Springer-Verlag: Springer-Verlag New York/Berlin), 362-378 · Zbl 0649.68075
[17] Mazurkiewicz, A., Concurrent Program Schemes and Their Interpretations, (DAIMI Rept. PB-78 (1977), Aarhus University)
[18] Reisig, W., Petri Nets, An Introduction (1985), Springer-Verlag: Springer-Verlag Berlin · Zbl 0555.68033
[19] Rozenberg, G.; Welzl, E., Boundary NLC graph grammars: Basic definitions, normal forms, and complexity, Inform. and Control, 69, 136-167 (1986) · Zbl 0608.68060
[20] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[21] Sudborough, I. H., On tape-bounded complexity classes and multihead finite automata, J. Comput. System Sci., 10, 62-76 (1975) · Zbl 0299.68031
[22] Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279-284 (1988) · Zbl 0638.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.