@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://aclanthology.org/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.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="schabes-1991-valid">
<titleInfo>
<title>The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar</title>
</titleInfo>
<name type="personal">
<namePart type="given">Yves</namePart>
<namePart type="family">Schabes</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>1991-feb 13-25</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Second International Workshop on Parsing Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Masaru</namePart>
<namePart type="family">Tomita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Martin</namePart>
<namePart type="family">Kay</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Robert</namePart>
<namePart type="family">Berwick</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Eva</namePart>
<namePart type="family">Hajicova</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aravind</namePart>
<namePart type="family">Joshi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ronald</namePart>
<namePart type="family">Kaplan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Makoto</namePart>
<namePart type="family">Nagao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Yorick</namePart>
<namePart type="family">Wilks</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Cancun, Mexico</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<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³)-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⁹)-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⁶)-time worst case behavior, O(n⁴)-time for unambiguous grammars and linear time for a large class of grammars.</abstract>
<identifier type="citekey">schabes-1991-valid</identifier>
<location>
<url>https://aclanthology.org/1991.iwpt-1.4</url>
</location>
<part>
<date>1991-feb 13-25</date>
<extent unit="page">
<start>21</start>
<end>30</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar
%A Schabes, Yves
%Y Tomita, Masaru
%Y Kay, Martin
%Y Berwick, Robert
%Y Hajicova, Eva
%Y Joshi, Aravind
%Y Kaplan, Ronald
%Y Nagao, Makoto
%Y Wilks, Yorick
%S Proceedings of the Second International Workshop on Parsing Technologies
%D 1991
%8 feb 13 25
%I Association for Computational Linguistics
%C Cancun, Mexico
%F schabes-1991-valid
%X 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³)-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⁹)-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⁶)-time worst case behavior, O(n⁴)-time for unambiguous grammars and linear time for a large class of grammars.
%U https://aclanthology.org/1991.iwpt-1.4
%P 21-30
Markdown (Informal)
[The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar](https://aclanthology.org/1991.iwpt-1.4) (Schabes, IWPT 1991)
ACL