Another Facet of LIG Parsing
<|reference_start|>Another Facet of LIG Parsing: 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.<|reference_end|>
@article{boullier1996another,
    title={Another Facet of LIG Parsing},
    author={Pierre Boullier (INRIA-Rocquencourt, Le Chesnay Cedex, France)},
    journal={arXiv preprint arXiv:cmp-lg/9604009},
    year={1996},
    archivePrefix={arXiv},
    eprint={cmp-lg/9604009},
    primaryClass={cmp-lg cs.CL}
}