Proceedings of the Annual Meeting of the Cognitive Science Society

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 language in linear time. In constrast, understanding language is not so easy for computers. Even ignoring problems of accuracy, natural language processing systems ane much slower than people aje. All current NL P 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 grammcirs. 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 been achieved, we will discuss possible improvements that may result in an average-case linear time algorithm.