Journal of Artificial Intelligence Research 5 (1996) 239-288
Submitted 3/96; published 11/96
(c) 1996 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

MUSE CSP: An Extension to the Constraint Satisfaction Problem

Randall A. Helzerman (helz@ecn.purdue.edu)
Mary P. Harper (harper@ecn.purdue.edu)

Abstract

This paper describes an extension to the constraint satisfaction problem (CSP) called MUSE CSP (MUltiply SEgmented Constraint Satisfaction Problem). This extension is especially useful for those problems which segment into multiple sets of partially shared variables. Such problems arise naturally in signal processing applications including computer vision, speech processing, and handwriting recognition. For these applications, it is often difficult to segment the data in only one way given the low-level information utilized by the segmentation algorithms. MUSE CSP can be used to compactly represent several similar instances of the constraint satisfaction problem. If multiple instances of a CSP have some common variables which have the same domains and constraints, then they can be combined into a single instance of a MUSE CSP, reducing the work required to apply the constraints. We introduce the concepts of MUSE node consistency, MUSE arc consistency, and MUSE path consistency. We then demonstrate how MUSE CSP can be used to compactly represent lexically ambiguous sentences and the multiple sentence hypotheses that are often generated by speech recognition algorithms so that grammar constraints can be used to provide parses for all syntactically correct sentences. Algorithms for MUSE arc and path consistency are provided. Finally, we discuss how to create a MUSE CSP from a set of CSPs which are labeled to indicate when the same variable is shared by more than a single CSP.

Table of Contents

1. Introduction
   1. The Constraint Satisfaction Problem
   2. The Multiply Segmented Constraint Satisfaction Problem
2. MUSE CSP and Constraint-based Parsing
   1. Parsing with Constraint Dependency Grammar
   2. Processing Lexically Ambiguous Sentences with CDG
   3. Lattice Example
   4. A Demonstration of the Utility of MUSE CSP Parsing
3. The MUSE CSP Arc Consistency Algorithm
   1. CSP Arc Consistency: AC-4
   2. MUSE AC-1
   3. The Running Time and Space Complexity of MUSE AC-1
   4. The Correctness of MUSE AC-1
   5. A Profile of MUSE AC-1
   6. Extracting Solutions from a MUSE CSP after MUSE AC-1
4. The MUSE CSP Path Consistency Algorithm
   1. MUSE PC-1
   2. The Running Time, Space Complexity, and Correctness of MUSE PC-1
5. Combining CSPs into a MUSE CSP
6. Conclusion
7. Acknowledgements
8. References