Solving the Correct-prefix Property for TAGs
Mark-Jan Nederhof · 1997
We present a new upper bound for the computational complexity of the parsing problem for TAGs, under the constraint that input is read from left to right in a way that errors in the input are observed as soon as possible, which is called the correct-prefix property. The former upper bound was O(n 9 ), which we now improve to O(n 6 ), which is the same as that of practical parsing algorithms for TAGs without the additional constraint of the correct-prefix property. Thereby we show that the correctprefix property does not require significant additional costs. 1 Introduction Traditionally, parsers and recognizers for regular and context-free languages process input from left to right. If a syntax error occurs in the input they often detect that error immediately after its position is reached. The position of the syntax error can be defined as the last input symbol of the shortest prefix which cannot be extended to be a correct sentence in the language L. In formal notation, this p...