Another Facet of LIG Parsing
| dc.creator | Boullier, Pierre | |
| dc.date | 1996-04-23 | |
| dc.date.accessioned | 2026-07-07T09:10:09Z | |
| dc.date.available | 2026-07-07T09:10:09Z | |
| dc.description | In this paper we present a new parsing algorithm for linear indexed grammars (LIGs) in the same spirit as the one described in (Vijay-Shanker and Weir, 1993) for tree adjoining grammars. For a LIG $L$ and an input string $x$ of length $n$, we build a non ambiguous context-free grammar whose sentences are all (and exclusively) valid derivation sequences in $L$ which lead to $x$. We show that this grammar can be built in ${\cal O}(n^6)$ time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this ${\cal O}(n^6)$ upper bound does not improve over previous results, the average case behaves much better. Moreover, practical parsing times can be decreased by some statically performed computations. | |
| dc.description | LaTex, 8 pages. To appear in Proceedings of ACL'96, Univ. of California, Santa Cruz, June 1996 | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9604009 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9604009 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151275 | |
| dc.subject | Computation and Language | |
| dc.title | Another Facet of LIG Parsing | |
| dc.type | text |