A Common Fallacy in Computational Linguistics

If you want a paper which shows the importance of careful, rigorous reasoning even about "obvious" matters, this one by Mehryar Mohri and Richard Sproat ought to do the trick. From the abstract comes the following:

The question of the computational complexity of natural language has attracted many linguists, formal language theory experts, mathematicians, and computer scientists over the last few decades. To determine the complexity of language, researchers have pointed out various complex morphological or syntactic constructions. But, the arguments used to infer from these observations a particular complexity, in particular the position of a language in Chomsky’s hierarchy, are often fallacious. Although this point has been noted many times, such arguments continue to flourish in the literature and even in some computational linguistics courses. The arguments share the same property and depend upon the same common fallacy. While in some cases it is possible to provide a correct formal proof of the complexity of a language, in many cases, the constructions in question cannot be used to demonstrate anything about the complexity of that language.

Here's the flawed line of argument in a nutshell:

Over the last forty years, starting with (Chomsky 1957), there have been a large number of papers addressing the issue of the computational complexity of natural language. Invariably, these take the following form: a particular construction of a language L is discovered that generates a language L′ ⊆ L which is at some well-defined position P′ in the Chomsky hierarchy, and from this it is concluded that L is at a position P ≥ P′. Say for example L′ is context-sensitive, so L is at least context-sensitive.

The problem, as the paper makes clear by example, is that it is perfectly possible for even a regular language to contain a context-sensitive subset!

This fallacy notwithstanding, it still does seem (to me at least) that context-free grammars are insufficiently powerful to fully capture the subtleties of human languages - though again, as the paper notes, strictly speaking, this is only a possibility if we make the seemingle outlandish assumption that sentences in human languages are essentially unbounded in length ...