Linguistics Stack Exchange is a question and answer site for professional linguists and others with an interest in linguistic research and theory. It only takes a minute to sign up.
Sign up to join this community
In computer science (especially computational complexity theory), problems can be classified to some complexity theory. For example, we say the travelling salesman problem belongs to NP-complete.
Parsing of a human-language text (e.g. English text) is also a computational problem. Can it be analyzed and classified to some complexity class? If yes, which class does it belong to and why?
While I have been unable to find any excerpts from the book in question, "A Fundamental Algorithm for Dependency Parsing" by M. Covington references "Computational Complexity And Natural Language" by Barton, Berwick, and Ristad, saying:
Barton, Berwick and Ristad... prove that when lexical ambiguity and agreement features are present — that is, when words can be ambiguous and can be labeled with attributes — natural language parsing is NP-complete.
I suspect this book may be of great interest to you.
This conclusion is backed up by "Computational complexity of problems on probabilistic grammars and transducers." by F. Casacuberta et al. which provides proofs that parsing of Stochastic Regular Grammars is NP-Hard as well as "Generation as Dependency Parsing" by A. Koller et al. which offers an ad hoc proof that parsing Topological Dependency Grammars is also NP-complete. As well as several other papers I found with a quick search on Google Scholar.
It depends on the framework. Within LFG, parsing is NP-compete in the worst case. However, Ron Kaplan argues that NL parsing is polynomial in the average case. In general, NL parsing is NP-complete because of the constraints associated with rules.
download\?doi\=10.1.1.119.776\&rep\=rep1\&type\=pdf Unification-based grammars and complexity classes, Anders Søgaard
Preliminary note: I tried to be as general as possible, but the variety of syntactic descriptions of Natural Language is such that it is unlikely that everyone will find here his preferred brand of syntax or parsing. For example, the parsing of lexicalized descriptions of language is not directly accounted for. I am not sure that this can be helped in any reasonnable way. My purpose here has been mainly to explore the range of questions that could or should be addressed when considering the complexity of natural language parsing.
The first point is that "Parsing of a human-language text" is an ill defined task. Complexity analysis is a mathematical endeavor which makes sense only within a mathematically well defined framework. You can therefore ask such a question only with respect to a given formal description of the language syntax.
Another preliminary point is that parsing is supposed to analyze syntax only, not semantics. But where is the border between syntax and semantics.
What is parsing ?
Parsing is always done with respect to a grammar (term used loosely to mean a description of the syntax) of a language in some appropriate formalism (formal framework). So the complexity classes are also classifying these formalisms.
Secondly, the concept of parsing itself should be precisely defined, It is clear that it is an algorithm taking as input a sentence (meaning only a linear sequence of words) and produces as output a structure that give a more explicit description of the sentence emphisizing the structural properties that make it belong to the language specified by the given grammar (I am trying very hard not to be too specific).
For example, with a generative grammar, the output of the parsing process may be a structure that describes precisely how the sentence can be generated by that grammar, when it is syntactically correct, i.e. when it belongs to the language described.
Furthermore, it is known that natural languages are generally syntactically ambiguous, i.e., that some syntactically correct sentences can be structurally described in several ways (generated in differents ways). Note that a sentence can be syntactically ambiguous, even though there is no semantic ambuiguity. Now the result expected from parsing could be :
In addition, the nature of the expected structural description may vary. Typically, the result of parsing a sentence according to a tree adjoining grammar (TAG) can be a (set of) derivation(s) tree(s) or a (set of) derived tree(s). Derivation trees and derived trees are distinct for TAG.
It is not obvious that the complexity is the same for all choices of what is expected as parsing result for a given formalism.
What is complexity ?
If the formalisms, and the result expected from the parsing process, are properly defined, it is of course possible to classify the parsing process for that formalism of in some complexity class, or more precisely to do a complexity analysis of the parsing process, as complexity classes come in many flavors : time complexity or space complexity, asymptotic worst case complexity or average complexity.
Though people often think of asymptotic worst case time complexity, it may make more sense in practice to consider average complexity. So such clssifications into complexity classes should be interpreted with care from a pragmatic point of view.
Another point is that complexity is often considered with respect to the size (number of words) of the sentence to be parsed. But complexity may also be analyzed with respect to the size of the grammar used to analyze a sentence. This is important as some people tend to increase the size of the syntax description in order to capture rarer or more subtle phenomena. This does not come for free.
Many formalisms are composed of a formal generative skeleton (such as context-free grammars) where various attributes (features, probabilities, ...) can be associated to the rules constituents, having to respect various constraints associated to the rule. The addition of these attributes and the respect of these constraints increases, often drastically, the complexity of the formalism, making it NP-hard, and even possibly Turing-complete (allowing you to encode as a parsing problem any algorithm you can dream of).
Of course there are zillions of subcases providing interesting complexity problems to people inclined to such studies.
One aspect commonly analyzed is the complexity of skeleton formalisms, without any attribute. Typically parsing context-free languages has time complexity O(n³), which is fairly low and quite tractable in practice. However, some structural organizations of the sentences cannot be captured by CF grammar. A classical example is cross-serial dependency.
Rather than add attributes to somehow encode the information necessary to handle such structures in a very general feature mechanism, some scientists consider that it is more effective, and possibly more perspicuous, to complexify a bit the skeleton formalism. This for example lead to the development of Tree Adjoining Grammars (time complexity O(n⁶)), then to a hierarchy of formalisms with increasing polynomial complexity, and the so-called mildly context-sensitive formalisms and Linear Context-Free rewriting systems. One remarkable aspect is that, though the polynomial worst-case complexity may seem high, structures producing high complexity may be few, so that things remain very tractable in practice.
This is to underscore, again, that complexity analysis does not necessarily tell the whole story.
