CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Uniform Parsing for Hyperedge Replacement Grammars
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0002-4696-9787
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0002-8722-5661
Faculty of Computer Science, TU Dresden.
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 [en]
graph grammars, hyperedge replacement, order-preserving graph grammars, uniform parsing problem
National Category
Computer Sciences
Research subject
Computing Science
Identifiers
URN: urn:nbn:se:umu:diva-153384OAI: oai:DiVA.org:umu-153384DiVA, id: diva2:1264041
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2018-11-19Bibliographically approved

Open Access in DiVA

fulltext(524 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 524 kBChecksum SHA-512
ae7769f1739a9ee0cde61822bbc2b80b752b07f89ce3372bd83a28c1d2a1b1405a8f3da5c6007e3266856732ca653df2c8c2305e2c47827cb77ba1a326511b6f
Type fulltextMimetype application/pdf

Other links

URL

Search in DiVA

By author/editor
Björklund, HenrikDrewes, FrankEricson, PetterStarke, Florian
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 90 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf