6533b82dfe1ef96bd1291165
RESEARCH PRODUCT
The complexity of graph languages generated by hyperedge replacement
Clemens Lautemannsubject
ParsingTheoretical computer scienceComputer Networks and CommunicationsComputer sciencebusiness.industryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Parsing expression grammarcomputer.software_genreTop-down parsingTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESParser combinatorS-attributed grammarTop-down parsing languageArtificial intelligenceL-attributed grammarbusinesscomputerComputer Science::Formal Languages and Automata TheorySoftwareNatural language processingInformation SystemsBottom-up parsingdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1990-04-01 | Acta Informatica |