Author: Steve Lytinen and Noriko Tomuro
Journal-ref: (1995) Proceedings of the 17th Annual Conference of the Cognitive Science Society, Pittsburgh, PA, pp. 666-670.
Understanding language is a seemingly effortless task for people. Not only can they understand the meaning of sentences with great accuracy, they do so quickly: in most cases, people understand languages in linear time. In contrast, understanding language is not so easy for computers. Even ignoring problems of accuracy, natural language processing systems are much slower than people are. All current NLP systems that fully analyze both the syntactic structure and semantic meaning of text fall short of human performance in this respect.
In this paper, we present an attempt to develop a linear time algorithm for parsing natural language using unification grammars. While the computational complexity of the algorithm is, in the worst case, no better than that of many other algorithms, empirical testing indicates improved average-case performance. Although linear performance has not yet achieved, we will discuss possible improvements that may result in an average-case linear time algorithm.
Paper: published paper (postscript XXXk)