tailieunhanh - Báo cáo khoa học: " CONSTRAINT PROPAGATION IN KIMMO SYSTEMS"

Taken abstractly, the two-level (Kimmo) morphological framework allows computationally difficult problems to arise. For example, N + 1 small a u t o m a t a 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 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 distinguishes them from more "global" SAT problems. By exploiting this structure, it may be possible to. | CONSTRAINT PROPAGATION IN KIMMO SYSTEMS G. Edward Barton Jr. . 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 formulas 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 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. 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 .