Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers

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,...

Descripción completa

Detalles Bibliográficos
Autores principales: Drewes, Frank, Hoffmann, Berthold, Minas, Mark
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7314914/
http://dx.doi.org/10.1007/978-3-030-51372-6_13
_version_ 1783550152819081216
author Drewes, Frank
Hoffmann, Berthold
Minas, Mark
author_facet Drewes, Frank
Hoffmann, Berthold
Minas, Mark
author_sort Drewes, Frank
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7314914
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73149142020-06-25 Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers Drewes, Frank Hoffmann, Berthold Minas, Mark Graph Transformation Article 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. 2020-05-31 /pmc/articles/PMC7314914/ http://dx.doi.org/10.1007/978-3-030-51372-6_13 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Drewes, Frank
Hoffmann, Berthold
Minas, Mark
Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title_full Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title_fullStr Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title_full_unstemmed Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title_short Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers
title_sort graph parsing as graph transformation: correctness of predictive top-down parsers
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7314914/
http://dx.doi.org/10.1007/978-3-030-51372-6_13
work_keys_str_mv AT drewesfrank graphparsingasgraphtransformationcorrectnessofpredictivetopdownparsers
AT hoffmannberthold graphparsingasgraphtransformationcorrectnessofpredictivetopdownparsers
AT minasmark graphparsingasgraphtransformationcorrectnessofpredictivetopdownparsers

Ejemplares similares