Emmanuel Roche (Mitsubishi Labs)
Accurately parsing natural language sentences requires very large scale lexical grammars. Rules of such grammars can roughly be classified as ``free" or "frozen" according to the variability of the arguments, e.g. complements. For instance, a rule describing a sentence like John eats potatoes would be called free whereas a rule describing a sentence like John kicks the bucket would be called frozen. Usually, grammar representations describe frozen rules as a particular case of free ones and assume that they can be treated as exceptions. Finite-state transducers not only give simple and efficient parsing strategies for very large scale grammars but that they also provide a natural and unified way of handling sentences in which free and frozen components are mixed in a complex manner.
In language processing, finite-state models are not a lesser evil that bring simplicity and efficiency at the cost of accuracy. On the contrary they provide a very natural framework to describe complex linguistic phenomena.