Accession Number:

ADA167782

Title:

The Computational Complexity of Two-Level Morphology.

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s):

Report Date:

1985-11-01

Pagination or Media Count:

39.0

Abstract:

Morphological analysis requires knowledge of the stems, affixes, combinatory patterns, and spelling-change processes of a natural language. The computational difficulty of the task can be clarified by investigating the computational characteristics of specific models of morphological processing. The use of finite-state machinery in the two-level model by Kimmo Koskenniemi gives it the appearance 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. However, another source of complexity in the exsting algorithms can be sharply reduced by changing the implementation of the dictionary component. A merged dictionary with bit-vectors reduces the number of choices among alternative dictionary subdivisions by allowing several subdivisions to be searched at once.

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE