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 formulas in N variables. However, the suspicion arises that natural-language problems may have a special structure --- not shard 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 distinguishes 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 combinatorial search.We have explored this possibility in a preliminary way by applying constraint propagation methods to Kimmo generation and recognition. Constraint propagation can succeed when the solution falls into place step-by-step through a chain of limited and local inferences, but it is insufficiently powerful to solve unnaturally hard SAT problems. Limited tests indicate that the constraint-propagation algorithm for Kimmo generation works for English, Turkish, and Warlpiri. When applied to a Kimmo system that encodes SAT problems, the algorithm succeeds on "easy" SAT problems but fails (as desired) on "hard" problems.

Morphological analysis must take into account the spelling-change processes of a language as well as its possible configurations of stems, affixes, and inflectional markings. The computational difficulty of the task can be clarified by investigating 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. The difficulty increases if unrestricted deletions (null characters) are allowed.

Modern linguistic theory attributes surface complexity to interacting subsystems of constraints. For instance, the ID/LP grammar formalism separates constraints on immediate dominance from those on linear order. Shieber's (1983) ID/LP parsing algorithm shows how to use ID and LP constraints directly in language processing, without expanding them into an intermediate "object grammar." However, Shieber's purported O(|G|2 n3) runtime bound underestimates the dificulty of ID/LP parsing. ID/LP parsing is actually NP-complete, and the worst-case runtime of Shieber's algorithm is actually exponential in grammar size. The growth of parser data structures causes the difficulty. Some computational and linguistic implications follow: in particular, it is important to note that despite its potential for combinatorial explosion, Shieber's algorithm remains better than the alternative of parsing an expanded object grammar.