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
Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
University of Bremen.
Universität der Bundeswehr München.
2020 (English)In: ICGT 2020. Lecture Notes in Computer Science / [ed] F. Gadducci and T. Kehrer, Springer, 2020Conference paper, Published paper (Refereed)
Abstract [en]

Hyperedge replacement (HR) allows to define context-free graph languages, but parsing is NP-hard in the general case. Predictive top-down (PTD) is an efficient, backtrack-free parsing algorithm for subclasses of HR and contextual HR grammars, which has been described and implemented in earlier work, based on a representation of graphs and grammar productions as strings. In this paper, we define PTD parsers for HR grammars by graph transformation rules and prove that they are correct.

Place, publisher, year, edition, pages
Springer, 2020.
Series
Lecture Notes in Computer Science ; 12150
Keywords [en]
graph transformation, hyperedge replacement, parsing, correctness
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-170870DOI: 10.1007/978-3-030-51372-6_13ISI: 000884307500013Scopus ID: 2-s2.0-85088207466ISBN: 978-3-030-51371-9 (print)ISBN: 978-3-030-51372-6 (electronic)OAI: oai:DiVA.org:umu-170870DiVA, id: diva2:1430699
Conference
13th International Conference on Graph Transformation (ICGT 2020), June 25-26, 2020
Available from: 2020-05-16 Created: 2020-05-16 Last updated: 2023-09-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Drewes, Frank

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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