Constraint Propagation in Kimmo Systems

CONSTRAINT PROPAGATION IN KIMMO SYSTEMS G. Edward Barton, Jr. M.I.T. Artificial Intelligence Laboratory 545 Technology Square Cambridge, MA 02139 ABSTRACT 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 gen- eration and recognition. Constraint propagation can suc- ceed when the solution falls into place step-by-step through a chain of limited and local inferences, but it is insuffi- ciently powerful to solve unnaturally hard SAT problems. Limited tests indicate that the constraint-propagation al- gorithm for Kimmo generation works for English, Turkish, and Warlpiri. When applied to a Kimmo system that en- codes SAT problems, the algorithm succeeds on "easy" SAT problems but fails (as desired) on "hard" problems. INTRODUCTION A formal computational model of a linguistic process makes explicit a set of assumptions about the nature of the process and the kind of information that it fundamentally involves. At the same time, the formal model will ignore some details and introduce others that are only artifacts of formalization. Thus, whenever the formal model and the actual process seem to differ markedly in properties, a natural assumption is that something has been missed in formalization -- though it may be difficult to say exactly what. When the difference is one of worst-case complexity, with the formal framework allowing problems to arise that are too difficult to be consistent with the received diffi- culty of actual problems, one suspects that the natural computational task might have significant features that the formalized version does not capture and exploit ef- fectively. This paper introduces a constraint propagation method for "two-lever' morphology that represents a pre- liminary attempt to exploit the features of local in]orrna- tion flow and linear separability that we believe are found in natural morphological-analysis problems. Such a local character is not shared by more difficult computational problems such as Boolean satisfiability, though such prob- lems can be encoded in the unrestricted two-level model. Constraint propagation is less powerful than backtracking search, but does not allow possibilities to build up in com- binatorial fashion. TWO-LEVEL MORPHOLOGY The mod~l of morphology developed by "two-level" Kimmo Koskenniemi is att~'active for putting morphological knowledge to use in processing. Two-level rules mediate the relationship between a lexieal string made up of mor- phemes from the dictionary and a surface string corre- sponding to the form a wo~d would have in text. Equiva- lently, the …

Content truncated to 500 words