Xerox Palo Alto Research Center Kenneth R. Beesley Xerox
Research Centre Europe This was the situation in the spring of
1980 when Kimmo Koskenniemi came to a conference on parsing that
Lauri Karttunen had organized at the University of Texas at
Austin. Also at the same conference were two Xerox researchers
from Palo Alto, Ronald M. Kaplan and Martin Kay. The four K's
discovered that all of them were interested and had been working
on the problem of morphological analysis. Koskenniemi went on to
Palo Alto to visit Kay and Kaplan at PARC. This was the
beginning of Two-Level Morphology, the first general model in
the history of computational linguistics for the analysis and
generation of morphologically complex languages. The language-
specific components, the lexicon and the rules, were combined
with a runtime engine applicable to all languages. In this
article we trace the development of the finite-state technology
that Two-Level Morphology is based on. Traditional phonological
grammars, formalized in the 1960s