umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Starke, Florian
Publications (1 of 1) Show all publications
Björklund, H., Drewes, F., Ericson, P. & Starke, F. (2018). Uniform Parsing for Hyperedge Replacement Grammars. Umeå: Umeå universitet
Open this publication in new window or tab >>Uniform Parsing for Hyperedge Replacement Grammars
2018 (English)Report (Other academic)
Abstract [en]

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomial-time algorithm that solves the uniform parsing problem for a restricted type of hyperedge-replacement grammars which we expect to be of interest for practical applications.

Place, publisher, year, edition, pages
Umeå: Umeå universitet, 2018. p. 21
Series
Report / UMINF, ISSN 0348-0542 ; 18.13
Keywords
graph grammars, hyperedge replacement, order-preserving graph grammars, uniform parsing problem
National Category
Computer Sciences
Research subject
business data processing
Identifiers
urn:nbn:se:umu:diva-153384 (URN)
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-01-07Bibliographically approved

Search in DiVA

Show all publications