The complexity of graph languages generated by hyperedge replacement |
| |
Authors: | Clemens Lautemann |
| |
Affiliation: | (1) Fachbereich Mathematik, Johannes Gutenberg-Universität, Saarstrasse 21, D-6500 Mainz, Federal Republic of Germany |
| |
Abstract: | 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.Parts of the results of this paper were presented at 15th ICALP, [La88b] |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|