Restricting the complexity of regular DNLC languages

  • IJsbrand Jan Albersberg
  • Joost Engelfriet
  • Grzegorz Rozenberg
Part II Technical Contributions
Part of the Lecture Notes in Computer Science book series (LNCS, volume 291)


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.

Key words

NLC graph grammars NP-complete NLOG componentbounded degree-bounded linear ordering 


  1. [AER]
    Aalbersberg, IJ.J., Ehrenfeucht, A., and Rozenberg, G., On the Membership Problem of Regular DNLC Grammars, Discrete Applied Mathematics 13 (1986) 79–85.CrossRefGoogle Scholar
  2. [AE]
    Aalbersberg, IJ.J. and Engelfriet, J., The recognition of trace languages, Techn. Rep. 86-18, University of Leiden, 1986.Google Scholar
  3. [AR1]
    Aalbersberg, IJ.J. and Rozenberg, G., Traces, Dependency Graphs and DNLC Grammars, Discrete Applied Mathematics 11 (1985) 299–306.CrossRefGoogle Scholar
  4. [AR2]
    Aalbersberg, IJ.J. and Rozenberg, G., Theory of Traces, Techn. Rep. 86-16, University of Leiden, 1986.Google Scholar
  5. [C]
    Cook, S.A., Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the Association for Computing Machinery 18 (1971) 4–18.Google Scholar
  6. [GJ]
    Garey, M.R. and Johnson, D.S., Computers and Intractability — a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.Google Scholar
  7. [H]
    Harary, F., Graph Theory, Addison-Wesley, Reading, Mass., 1969.Google Scholar
  8. [HU]
    Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979.Google Scholar
  9. [JR]
    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.CrossRefGoogle Scholar
  10. [LW]
    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–30CrossRefGoogle Scholar
  11. [Ma]
    Mazurkiewicz, A., Concurrent Program Schemes and their Interpretations, DAIMI Rept. PB — 78, Aarhus University, 1977.Google Scholar
  12. [R]
    Reisig, W., Petri Nets, an Introduction, Springer, Berlin, 1985.Google Scholar
  13. [RW]
    Rozenberg, G. and Welzl, E., Boundary NLC Graph Grammars: Basic Definitions, Normal Forms, and Complexity, Information and Control 69 (1986) 136–167CrossRefGoogle Scholar
  14. [S]
    Salomaa, A., Formal Languages, Academic Press, New York, 1973.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1987

Authors and Affiliations

  • IJsbrand Jan Albersberg
    • 1
  • Joost Engelfriet
    • 1
  • Grzegorz Rozenberg
    • 1
  1. 1.Department of Computer ScienceUniversity of LeidenLeidenThe Netherlands

Personalised recommendations