Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars

The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method av...

Descripción completa

Detalles Bibliográficos
Autores principales: Wang, Yi, Zeng, XiaoQin, Ding, Han
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2015
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4664237/
https://www.ncbi.nlm.nih.gov/pubmed/26618493
http://dx.doi.org/10.1371/journal.pone.0142776
_version_ 1782403400925708288
author Wang, Yi
Zeng, XiaoQin
Ding, Han
author_facet Wang, Yi
Zeng, XiaoQin
Ding, Han
author_sort Wang, Yi
collection PubMed
description The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method avoids the subgraph isomorphism judgment and selects the productions specifically, so that the time-complexity is greatly reduced.
format Online
Article
Text
id pubmed-4664237
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-46642372015-12-10 Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars Wang, Yi Zeng, XiaoQin Ding, Han PLoS One Research Article The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method avoids the subgraph isomorphism judgment and selects the productions specifically, so that the time-complexity is greatly reduced. Public Library of Science 2015-11-30 /pmc/articles/PMC4664237/ /pubmed/26618493 http://dx.doi.org/10.1371/journal.pone.0142776 Text en © 2015 Wang et al http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Wang, Yi
Zeng, XiaoQin
Ding, Han
Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title_full Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title_fullStr Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title_full_unstemmed Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title_short Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars
title_sort research on the top-down parsing method for context-sensitive graph grammars
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4664237/
https://www.ncbi.nlm.nih.gov/pubmed/26618493
http://dx.doi.org/10.1371/journal.pone.0142776
work_keys_str_mv AT wangyi researchonthetopdownparsingmethodforcontextsensitivegraphgrammars
AT zengxiaoqin researchonthetopdownparsingmethodforcontextsensitivegraphgrammars
AT dinghan researchonthetopdownparsingmethodforcontextsensitivegraphgrammars

Ejemplares similares