Another Facet of LIG Parsing

Details Another Facet of LIG Parsing Another Facet of LIG Parsing

1996-04-23

arxiv.org/abs/cmp-lg/9604009v1

Computer Science

Computation and Language

LaTex, 8 pages. To appear in Proceedings of ACL'96, Univ. of California, Santa Cruz, June 1996

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Another Facet of LIG Parsing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Another Facet of LIG Parsing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Another Facet of LIG Parsing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-490709