Paper: Constraint Propagation In KIMMO Systems

ACL ID P86-1008
Title Constraint Propagation In KIMMO Systems
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1986

Taken abstractly, the two-level (Kimmo) morphological framework allows computationally difficult problems to arise. For example, N + 1 small automata are sufficient to encode the Boolean satisfiability problem (SAT) for for- mulas in N variables. However, the suspicion arises that natural-language problems may have a special structure -- not shared with SAT -- that is not directly captured in the two-level model. In particular, the natural problems may generally have a modular and local nature that dis- tinguishes them from more "global" SAT problems. By exploiting this structure, it may be possible to solve the natural problems by methods that do not involve combi- natorial search. We have explored this possibility in a preliminary way by applying constraint propagation methods to Kimmo g...