Approximating Parikh Images for Generating Deterministic Graph Parsers
F. Drewes, B. Hoffmann, and M. Minas. Software Technologies: Applications and Foundations -- STAF 2016 Collocated Workshops: DataMod, GCM, HOFM, MELO, SEMS, VeryComp, Vienna Austria, July 4-8, 2016, Revised Selected Papers, page 112--128. Springer International Publishing, (2016)
DOI: 10.1007/978-3-319-50230-4_9
Abstract
The Parikh image of a word abstracts from the order of its letters. Parikh's famous theorem states that the set of Parikh images of a context-free string language forms a semilinear set that can be effectively computed from its grammar. In this paper we study the computation of Parikh images for graph grammars defined by contextual hyperedge replacement (CHR). Our motivation is to generate efficient predictive top-down (PTD) parsers for a subclass of CHR grammars. We illustrate this by describing the subtask that identifies the nodes of the input graph that parsing starts with.
%0 Conference Paper
%1 drewes-hoffmann-minas:16
%A Drewes, Frank
%A Hoffmann, Berthold
%A Minas, Mark
%B Software Technologies: Applications and Foundations -- STAF 2016 Collocated Workshops: DataMod, GCM, HOFM, MELO, SEMS, VeryComp, Vienna Austria, July 4-8, 2016, Revised Selected Papers
%D 2016
%E Milazzo, Paolo
%E Varró, Dániel
%E Wimmer, Manuel
%I Springer International Publishing
%K 2016 DiaPlan GraGra GraphParsing Parikh myown parsing
%P 112--128
%R 10.1007/978-3-319-50230-4_9
%T Approximating Parikh Images for Generating Deterministic Graph Parsers
%U http://dx.doi.org/10.1007/978-3-319-50230-4_9
%X The Parikh image of a word abstracts from the order of its letters. Parikh's famous theorem states that the set of Parikh images of a context-free string language forms a semilinear set that can be effectively computed from its grammar. In this paper we study the computation of Parikh images for graph grammars defined by contextual hyperedge replacement (CHR). Our motivation is to generate efficient predictive top-down (PTD) parsers for a subclass of CHR grammars. We illustrate this by describing the subtask that identifies the nodes of the input graph that parsing starts with.
%@ 978-3-319-50230-4
@inproceedings{drewes-hoffmann-minas:16,
abstract = {The Parikh image of a word abstracts from the order of its letters. Parikh's famous theorem states that the set of Parikh images of a context-free string language forms a semilinear set that can be effectively computed from its grammar. In this paper we study the computation of Parikh images for graph grammars defined by contextual hyperedge replacement (CHR). Our motivation is to generate efficient predictive top-down (PTD) parsers for a subclass of CHR grammars. We illustrate this by describing the subtask that identifies the nodes of the input graph that parsing starts with.},
added-at = {2017-09-28T18:19:47.000+0200},
author = {Drewes, Frank and Hoffmann, Berthold and Minas, Mark},
bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-319-50230-4_9},
biburl = {https://www.bibsonomy.org/bibtex/25b3138a5691738ad6957cac680a4426e/minas},
booktitle = {Software Technologies: Applications and Foundations -- STAF 2016 Collocated Workshops: DataMod, GCM, HOFM, MELO, SEMS, VeryComp, Vienna Austria, July 4-8, 2016, Revised Selected Papers},
crossref = {STAF2016-workshops},
date-added = {2017-02-15 13:04:05 +0000},
date-modified = {2017-07-06 09:17:20 +0000},
doi = {10.1007/978-3-319-50230-4_9},
editor = {Milazzo, Paolo and Varr{\'o}, D{\'a}niel and Wimmer, Manuel},
interhash = {8ddc00d0ce3770f711bb8e2b969e3024},
intrahash = {5b3138a5691738ad6957cac680a4426e},
isbn = {978-3-319-50230-4},
keywords = {2016 DiaPlan GraGra GraphParsing Parikh myown parsing},
pages = {112--128},
publisher = {Springer International Publishing},
timestamp = {2017-09-28T19:00:00.000+0200},
title = {Approximating {P}arikh Images for Generating Deterministic Graph Parsers},
url = {http://dx.doi.org/10.1007/978-3-319-50230-4_9},
year = 2016
}