Abstract
Regular directed node-label controlled graph grammars (RDNLC grammars) originated from the need for a formal description of event structure languages (related to Petri nets) and of dependence graph languages (related to trace languages). In this framework complexity problems concerning event structure languages and dependence graph languages can be reduced to complexity problems concerning RDNLC languages.
It is known that the membership problem for RDNLC languages is NP-complete. This paper describes borderlines between NP-complete and less complex RDNLC languages. Moreover, for some of those less complex cases, the corresponding techniques for deciding the membership problem are provided.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aalbersberg, IJ.J., Ehrenfeucht, A., and Rozenberg, G., On the Membership Problem of Regular DNLC Grammars, Discrete Applied Mathematics 13 (1986) 79–85.
Aalbersberg, IJ.J. and Engelfriet, J., The recognition of trace languages, Techn. Rep. 86-18, University of Leiden, 1986.
Aalbersberg, IJ.J. and Rozenberg, G., Traces, Dependency Graphs and DNLC Grammars, Discrete Applied Mathematics 11 (1985) 299–306.
Aalbersberg, IJ.J. and Rozenberg, G., Theory of Traces, Techn. Rep. 86-16, University of Leiden, 1986.
Cook, S.A., Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the Association for Computing Machinery 18 (1971) 4–18.
Garey, M.R. and Johnson, D.S., Computers and Intractability — a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
Harary, F., Graph Theory, Addison-Wesley, Reading, Mass., 1969.
Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979.
Janssens, D. and Rozenberg, G., A Characterization of Context-Free String Languages by Directed Node-Label Controlled Graph Grammars, Acta Informatica 16 (1981) 63–85.
Lange, K.-J. and Welzl, E., String Grammars with Disconnecting or a Basic Root of the Difficulty in Graph Grammar Parsing, Discrete Applied Mathematics 16 (1987) 17–30
Mazurkiewicz, A., Concurrent Program Schemes and their Interpretations, DAIMI Rept. PB — 78, Aarhus University, 1977.
Reisig, W., Petri Nets, an Introduction, Springer, Berlin, 1985.
Rozenberg, G. and Welzl, E., Boundary NLC Graph Grammars: Basic Definitions, Normal Forms, and Complexity, Information and Control 69 (1986) 136–167
Salomaa, A., Formal Languages, Academic Press, New York, 1973.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albersberg, I.J., Engelfriet, J., Rozenberg, G. (1987). Restricting the complexity of regular DNLC languages. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds) Graph-Grammars and Their Application to Computer Science. Graph Grammars 1986. Lecture Notes in Computer Science, vol 291. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18771-5_51
Download citation
DOI: https://doi.org/10.1007/3-540-18771-5_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18771-4
Online ISBN: 978-3-540-48178-2
eBook Packages: Springer Book Archive