Umeå University's logo

umu.sePublications
Change search
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. Digital and Cognitive Musicology Lab, Ecole Polytechnique F´ed´erale de Lausanne, Switzerland.ORCID iD: 0000-0002-8722-5661
Faculty of Computer Science, TU Dresden, Germany.ORCID iD: 0000-0003-2360-9364
2021 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 118, p. 1-27Article in journal (Refereed) Published
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
Elsevier, 2021. Vol. 118, p. 1-27
Keywords [en]
parsing, graph language, graph grammar, abstract meaning representation
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-177125DOI: 10.1016/j.jcss.2020.10.002ISI: 000615930900001Scopus ID: 2-s2.0-85097717738OAI: oai:DiVA.org:umu-177125DiVA, id: diva2:1504600
Available from: 2020-11-29 Created: 2020-11-29 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

fulltext(684 kB)249 downloads
File information
File name FULLTEXT01.pdfFile size 684 kBChecksum SHA-512
6b2bb34caa9e900c9dbb45d63070212fea3a770d697848d66788ca79eba3550ac8ab7b24b84a98453d94e42c635d27689da9e6ed10d677f7b5e0fd389a0f780d
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Björklund, HenrikDrewes, FrankEricson, Petter

Search in DiVA

By author/editor
Björklund, HenrikDrewes, FrankEricson, PetterStarke, Florian
By organisation
Department of Computing Science
In the same journal
Journal of computer and system sciences (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 249 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 351 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