Parsing Free Word-Order Languages in Polynomial Time
<|reference_start|>Parsing Free Word-Order Languages in Polynomial Time: We present a parsing algorithm with polynomial time complexity for a large subset of V-TAG languages. V-TAG, a variant of multi-component TAG, can handle free-word order phenomena which are beyond the class LCFRS (which includes regular TAG). Our algorithm is based on a CYK-style parser for TAGs.<|reference_end|>
@article{becker1994parsing,
    title={Parsing Free Word-Order Languages in Polynomial Time},
    author={Tilman Becker (U. Penn.) and Owen Rambow (Paris 7)},
    journal={In {\em 3e Colloque International sur les Grammaires d'Arbres
  Adjoints (TAG+3)}},
    year={1994},
    number={TALANA-RT-94-01, TALANA, Universite' Paris 7, 1994},
    archivePrefix={arXiv},
    eprint={cmp-lg/9411008},
    primaryClass={cmp-lg cs.CL}
}