Uniquely Parallel Parsable Unification Grammars
Summary :
A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.
- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.21-27
- Publication Date
- 2001/01/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Jia LEE, Kenichi MORITA, "Uniquely Parallel Parsable Unification Grammars" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 1, pp. 21-27, January 2001, doi: .
Abstract: A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_1_21/_p
Copy
@ARTICLE{e84-d_1_21,
author={Jia LEE, Kenichi MORITA, },
journal={IEICE TRANSACTIONS on Information},
title={Uniquely Parallel Parsable Unification Grammars},
year={2001},
volume={E84-D},
number={1},
pages={21-27},
abstract={A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Uniquely Parallel Parsable Unification Grammars
T2 - IEICE TRANSACTIONS on Information
SP - 21
EP - 27
AU - Jia LEE
AU - Kenichi MORITA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2001
AB - A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.
ER -
English
