caa a22 4500 467989893 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900401xx s 000 0 eng 10.1007/BF00289017 doi (NATIONALLICENCE)springer-10.1007/BF00289017 Lautemann Clemens Fachbereich Mathematik, Johannes Gutenberg-Universität, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany aut The complexity of graph languages generated by hyperedge replacement [Elektronische Daten] [Clemens Lautemann] Summary: Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing. Springer-Verlag, 1990 Acta Informatica Springer-Verlag 27/5(1990-04-01), 399-421 0001-5903 27:5<399 1990 27 236 https://doi.org/10.1007/BF00289017 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00289017 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lautemann Clemens Fachbereich Mathematik, Johannes Gutenberg-Universität, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 27/5(1990-04-01), 399-421 0001-5903 27:5<399 1990 27 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer