Computational Complexity in Two-Level Morphology

COMPUTATIONAL COMPLEXITY IN TWO-LEVEL MORPHOLOGY G. Edward Barton, Jr. M.I.T. Artificial Intelligence Laboratory 545 Technology Square Cambridge, MA 02139 ABSTRACT Morphological analysis must take into account the spelling-change processes of a language as well as its possi- ble configurations of stems, affixes, and inflectional mark- ings. The computational difficulty of the task can be clari- fied by investigating specific models of morphological pro- cessing. The use of finite-state machinery in the "two- level" model by Kimmo Koskenniemi gives it the appear- ance of computational efficiency, but closer examination shows the model does not guarantee efficient processing. Reductions of the satisfiability problem show that finding the proper lexical/surface correspondence in a two-level generation or recognition problem can be computationally difficult. The difficulty increases if unrestricted deletions (null characters) are allowed. INTRODUCTION The "dictionary lookup" stage in a natural-language system can involve much more than simple retrieval. In- flectional endings, prefixes, suffixes, spelling-change pro- cesses, reduplication, non-concatenative morphology, and clitics may cause familiar words to show up in heavily dis- guised form, requiring substantial morphological analysis. Superficially, it seems that word recognition might poten- tially be complicated and difficult. This paper examines the question more formally by in- vestigating the computational characteristics of the "two- level" model of morphological processes. Given the kinds of constraints that can be encoded in two-level systems, how difficult could it be to translate between lexical and surface forms? Although the use of finite-state machin- ery in the two-level model gives it the appearance of com- putational efficiency, the model itself does not guarantee efficient processing. Taking the Kimmo system (Kart- tunen, 1983) for concreteness, it will be shown that the general problem of mapping between ]exical and surface forms in two-level systems is computationally difficult in the worst case; extensive backtracking is possible. If null characters are excluded, the generation and recognition problems are NP-complete in the worst case. If null charac- ters are completely unrestricted, the problems is PSPACE- complete, thus probably even harder. The fundamental difficulty of the problems does not seem to be a precompi- lation effect. In addition to knowing the stems, affixes, and co- occurrence restrictions of a language, a successful morpho- logical analyzer must take into account the spelling-change processes that often accompany affixation. In English, the program must expect love+ing to appear as loving, fly+s as flies, lie+ing as lying, and big+er as bigger. Its knowledge must be sufficiently sophisticated to distin- guish such surface forms as hopped and hoped. Cross- linguistically, spelllng-change processes may span either a limited or a more extended range of characters, and the material that triggers a change may occur either before or after the character that is affected. (Reduplication, a com- plex copying process that may also be found, will not be considered here.) The Kimmo system described by Karttunen (1983} is attractive for putting morphological knowledge to use in processing. Kimmo is an implementation of the "two-level" model of morphology that Kimmo Koskenniemi proposed and developed in his Ph.D. thesis. I A …

Content truncated to 500 words