Paper: Computational Complexity In Two-Level Morphology

ACL ID P86-1009
Title Computational Complexity In Two-Level Morphology
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1986

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.