@inproceedings{schabes-1991-valid,
    title = "The Valid Prefix Property and Left to Right Parsing of {T}ree-{A}djoining {G}rammar",
    author = "Schabes, Yves",
    editor = "Tomita, Masaru  and
      Kay, Martin  and
      Berwick, Robert  and
      Hajicova, Eva  and
      Joshi, Aravind  and
      Kaplan, Ronald  and
      Nagao, Makoto  and
      Wilks, Yorick",
    booktitle = "Proceedings of the Second International Workshop on Parsing Technologies",
    month = feb # " 13-25",
    year = "1991",
    address = "Cancun, Mexico",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-emnlp/1991.iwpt-1.4/",
    pages = "21--30",
    abstract = "The valid prefix property (VPP), the capability of a left to right parser to detect errors as soon as possible, often goes unnoticed in parsing CFGs. Earley{'}s parser for CFGs (Earley, 1968; Earley, 1970) maintains the valid prefix property and obtains an $O(n^3)$-time worst case complexity, as good as parsers that do not maintain such as the CKY parser (Younger, 1967; Kasami, 1965). Contrary to CFGs, maintaining the valid prefix property for TAGs is costly. In 1988, Schabes and Joshi proposed an Earley-type parser for TAGs. It maintains the valid prefix property at the expense of its worst case complexity ($O(n^9)$-time). To our knowledge, it is the only known polynomial time parser for TAGs that maintains the valid prefix property. In this paper, we explain why the valid prefix property is expensive to maintain for TAGs and we introduce a predictive left to right parser for TAGs that does not maintain the valid prefix property but that achieves an $O(n^6)$-time worst case behavior, $O(n^4)$-time for unambiguous grammars and linear time for a large class of grammars."
}