On binary constraint problems

ABSTRACT

The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski. The concept of path-consistency plays a central role. Algorithms for path-consistency can be implemented on matrices of relations and on matrices of elements from a relation algebra. We give an example of a 4-by-4 matrix of infinite relations on which on iterative local path-consistency algorithm terminates. We give a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time. Specific relation algebras arising from interval constraint problems are also studied: the Interval Algebra, the Point Algebra, and the Containment Algebra.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: ~ALLEN, J. F., AND HAYES, P. J. 1987. Moments and points in an interval-based temporal logic. ~Tech. Rept. TR180. Dept. Comput. Sci., Umv. Rochester, Rochester, N.Y., Dec.
• 3: ~BURRIS, S., AND SANKAPPANAVAR, H. P. 1981. ,4 Course tn UnwersalAlgehra. Springer-Verlag.
• 4: ~CHANG, C. C., AND KEISLER, n. J. 1973. Model Theoo', North-Holland, New York.
• 5: ~CHIN, m. n., AND TARSKI, A. 1951. Distributive and modular laws in the arithmetic of relation ~algebras. Unit'. Calif. Publications tn Mathcrnatics, New Series 1, 9, 341 384.
• 6: Rina Dechter , Itay Meiri , Judea Pearl, Temporal constraint networks, Artificial Intelligence, v.49 n.1-3, p.61-95, May 1991 [doi>10.1016/0004-3702(91)90006-6]
• 7: R. Dechter , J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, v.34 n.1, p.1-38, Dec. 1987 [doi>10.1016/0004-3702(87)90002-6]
• 8: ~DE MORGAN, A. 1864. On the syllogism, no. IV, and on the logic of relations. Trans. Cambndge ~Philos. Soc. JO, 331-358. (Written 1859, presented to C.P.S. 4/23/1860, published as above, ~reprinted in {De Morgan, 1966}).
• 9: ~DE MORGAN, A. 1966. On tile Syllogism and other Logical ~DWings. Yale University Press, New ~ Haven, Conn.
• 10: ~EILENBERG, S., AND MAC LANE, S. 1945. Relations between homology and homotopy groups of ~spaces. Ann. Math. 46, 480 509.
• 11: ~EGGLESTON, H. G. 1969. Convexity. Cambridge University Press, Cambridge, Mass.
• 12: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• 13: ~GOLUMBIC, M. C., AND SHAMIR, R. 1991. Complexity and algorithms for reasoning about time: A ~graph-theoretic approach. RUTCOR Res. Rept. RRR #22-91. Rutgers Center for Operations ~Research, New Brunswick, N.J.
• 14: Hans Werner Gusgen, CONSAT: a system for constraint satisfaction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 15: ~HELLY, E. 1923. 0bet Mengen convexer K6rper mit gemeinschaftlichen Punkten. Jahr. Deutsch. ~Math. Verein. 32, 175-176.
• 16: ~IMIELINSKI, T., AND LIPSKI, W., JR., 1984. The relational model of data and cylindric algebras. J. ~Comput. Syst. Sci. 28, 80-102.
• 17: ~J6NSSON, B. 1982. Varieties of relation algebras. Alg. Untt,et'salis 15, 273-298.
• 18: ~J6NSSON, B. 1991. The theory of binary relations. In Algebraic Logic. Colloquia Mathematica ~Societis Jfinos Bolyai, vol. 54. North-Holland, Amsterdam, The Netherlands, pp. 245-292.
• 19: ~J6NSSON, B., AND TARSKI, A. 1952. Boolean algebras with operators II. Amer. J. Math. 74, ~ 127-162.
• 20: ~KAUTZ, J. h., AND LADKIN, P. B. 1991. Integrating metric and qualitative temporal reasoning. In ~ Proceedings of AAAI-91, the 9th National Conferetzce on AI. AAAI Press, Menlo Park, Calif., pp. ~ 241-246.
• 21: ~LADKIN, P. B. 1986. Time representation: A taxonomy of interval relations. In Proceedings of the ~5th National Conference on AI (AAAI-86). Morgan-Kaufmann, San Mateo, CaliL pp. 360-366.
• 22: ~LADrIN, P. B. 1987a. Models of axioms for time intervals. In Proceedings of AAAI-87, the 6th ~ National Conference on Artificial lntelhgence. Morgan-Kaufmann, San Mateo, Calif., pp. 234-239, ~(Kestrel Institute Tech. KES.U.87.4. (long version), Palo Alto, Calif.
• 23: ~LADK{N, P. B. 1987b. The logic of time representation. Ph.D. dissertation, Univ. California at ~ Berkeley, Berkeley, Calif., 130, (Kestrel Institute Tech. Rep. KES.U.87.13, Palo Alto, Calif. ~1987).
• 24: ~LADKIN, P. B. 1988. Satisfying first-order constraints about time intervals. In Proceedings of the ~ 7th National Conference on AI, (AAAI-88). Morgan-Kaufmann, San Mateo, Calif., pp. 512-517 ~(Constraint satisfaction in time interval structures I: Convex intervals. Kestrel Institute Tech. ~Rep. KES.U.87.11 (long version), Palo Alto, Calif. 1987).
• 25: ~LADKIN, P. B. 1990. Constraint reasoning with intervals: A tutorial, survey, and bibliography. ~ Tech. Rep. TR-90-059. International Computer Science Institute, Berkeley, Calif., Sept.
• 26: ~LADK1N, P. B., AND MADDUX, R. D. 1987. The algebra of convex time intervals, Kestrel Institute ~Tech. Rep. KES.U.87.2, 1987 (short version); Representation and reasoning with convex time ~intervals (Kestrel Institute Tech. Rep. KES.U.88.2. Palo Alto, Calif., 1988 (long version)).
• 27: ~LADKIN, P. B., AND MADDUX, R. D. 1988. On binary constraint networks. Kestrel Institute Tech. ~Rep. KES.U.88.8, Palo Alto, Calif.
• 28: ~LADKIN, P. U., AND REINEFELD, A. 1991. How to solve interval constraint networks: The ~ definitive answer--Probably. Tech. Rep. TR-91-063. International Computer Science Institute, ~Berkeley, Calif., Nov.
• 29: ~LIGOZAT, G. 1990a. Weak representations of interval algebras. In Proceedfizgs of AAAI-90, the ~8th National Conference on Arttficial Intelligence. AAAI Press, Menlo Park, Calif., pp. 715-720.
• 30: ~LIGOZAT, G. 1990b. Intervalles g6ndralis6s I, II. Comptes Rendues de l'Academie des Sciences de ~ Paris', t. 310, Sdrie I, 225-228 and 299-302.
• 31: ~LIGOZAT, G. 1991. On generalized interval calculi. In Proceedings of AAAI-91, the 9th National ~Conference on Artificial Intelligence. AAAI Press, Menlo Park, Calif., pp. 234 240.
• 32: Gérard Ligozat , Hélène Bestougeff, On relations between intervals, Information Processing Letters, v.32 n.4, p.177-182, Sept 1, 1989 [doi>10.1016/0020-0190(89)90040-9]
• 33: ~LYNDON, R. C. 1950. The representation of relational algebras. Ann. Math. Ser. 2, 51,707-729.
• 34: ~LYNDON, R. C. 1956. The representation of relational algebras, II. Ann. Math. Set. 2, 63, ~ 294-307.
• 35: ~MACKWORTH, h. K. 1977. Consistency in networks of relations. Artif. Int. 8, 99-118.
• 36: ~MACKWORTH. A. K. 1987. Constraint satisfaction. In Ellcyclopedia of Artificial Intalligance, g. ~ Shapiro, Ed. Wiley Interscience, New York, pp. 205-211.
• 37: Alan K. Mackworth , Eugene C. Freuder, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, v.25 n.1, p.65-74, Jan. 1985 [doi>10.1016/0004-3702(85)90041-4]
• 38: ~MADDUX, R. D. 1982. Some varieties containing relation algebras. Trans. AMS 272, 501 526.
• 39: ~MADDUX, R. D. 1983. A sequent calculus for relation algebras. Ann. Pure Appl. Logtc 25, ~73-101.
• 40: ~MADDUX, R. D. 1989. Nonfinite axiomatizability results for cylindric and relation algebras. J. ~ Svmb. Logic 54, 951 974.
• 41: ~MADDUX, R. D. 1991a. Pair-dense relation algebras. Trans. AMS 328, 83-131.
• 42: ~MADDUX, R. D. 1991b. Introductory course on relation algebras, finite-dimensional cylindric ~ algebras, and their interconnections. In Algebratc Logic, Colloquia Mathematica Socletls Jfinos ~ Bolyai, vol. 54, North-Holland, Amsterdam, The Netherlands, pp. 361-392.
• 43: ~MADDUX, R. D. 1991c. The neat embedding problem and the number of variables required in ~proofs. Proc. Amer. Math. Soc. 112, 195-202.
• 44: ~MADDUX, R. D. 1991d. The origin of relation algebras in the development and axiomatization of ~ the calculus of relations, Studia Logica 50, 3/4, 421-455.
• 45: ~MEmI, I. 1991. Combining qualitative and quantitative constraints in temporal reasoning. In ~Proceedings of AAAI-91, the 9th Nanonal Conference on AI. AAAI Press, 1991, pp. 260-267.
• 46: Itay Meiri, Temporal reasoning: a constraint-based approach, University of California at Los Angeles, Los Angeles, CA, 1992
• 47: Roger Mohr , Thomas C. Henderson, Arc and path consistence revisited, Artificial Intelligence, v.28 n.2, p.225-233, March 1986 [doi>10.1016/0004-3702(86)90083-4]
• 48: ~MONK, J. D., 1964. On representable relation algebras. Mteh. Math. J. 11,207-210.
• 49: ~MONTANARI, U. 1974. Networks of constraints: Fundamental properties and applications to ~picture processing, bzform. Sci. 7, 95-132.
• 50: Klaus Nökel, Temporally distributed symptoms in technical diagnosis, Springer-Verlag New York, Inc., New York, NY, 1991
• 51: ~PEIRCE, C. S. 1870. Description of a notation for the logic of relatives, resulting from an ~ amplification of the concepnons of Boole's calculus of logic. Mere. Amer. Acad. Scz. 9~ ~317-378. (Reprint by Welch, Bigelow and Co., Cambridge, Mass., 1870, pp. 1-62. Also ~reprinted in {Peirce, 1933}.)
• 52: ~PEtRCE, C. S. 1883. Note B: The logic of relatives. In Studws m Logw by Members of the Johns ~Hopkins Unwerszty. C. S. Peirce, Ed. Little, Brown, and Co., Boston, Mass., pp. 187-203. ~ (Reprinted in {Pelrce, 1933} and {Peirce, 1983}.)
• 53: ~PEIRCE, C. S. 1933. Collected Papers, Volume III, Charles Hartshorne and Paul Weiss, Eds. ~Harvard University Press, Cambridge, U K.
• 54: ~PEIRCE, C. S. 1983. Studies tn Logzc by Members of the Johns Hopkins Unwerst~. C. S. Pelrce, Ed. ~ (Introduction by M. H. Fisch, Preface by A. Eschbach). John Benjamins Publishing Co., ~ Amsterdam and Philadelphia.
• 55: ~REtNEFELD, A., AND LADKiN, P. U. 1992. Fast solution of large interval constraint networks. In ~ Proceedings oj the 9th Cana&au Conference on At:tificial bztelligence, A1'92, J. Glasgow and R. ~Hedley, Eds. Morgan Kaufman, San Mateo, Calif., pp. 156-192.
• 56: ~SCHRODER, F. W. K. E. 1895. Vorlesungen iiber die Algebra der Logik ( exacte Logtk ), Dntter Band, ~ Algebra und Logik der Relatice, Erste Abtezhmg. Leipzig. (Reprinted Chelsea Publishing Co., ~ N.Y., 1966.)
• 57: ~SUSSWEIN, S. 1991. Parallel path consistency. M.S. d~ssertation. Dept. Comput. Sci., Univ. Utah ~at Salt Lake City, Salt Lake City, Ut.
• 58: ~SUSSWE1N, S., HENDERSON, T. C., ZACHARY, J., HINKER, P., HANSEN, C., AND MARSDEN, G. 1991. ~ Parallel path consistency. Tech. Rep. UUCS-91-(lll). Univ. Utah at Salt Lake City, Salt Lake ~C~ty, Ut.
• 59: TARSKL A. 1941. On the calculus of relations. J. Symb. Logzc 6, 73-80.
• 60: ~TARSKI, A. 1955. Contribunons to the theory of models, III. Konmlclokle, Nederlandse~qkaclemie ~t'an Wetenschappen. Proceedings. Series A. Mathemattcal Sctences ( lndagattones Mathematlcae ~17) 58, 56-64.
• 61: ~TARSKI, A., AND GIVANT, S. R. 1987. A formalization of set theory without variables. In ~Colloquium Pubhcanons tn Mathematzcs, vol. 41. American Mathematics Society, Providence, ~ R.I.
• 62: ~VAN mEEK, P. G., AND COHEN, R. 1989/ 1990. Approximation algorithms for temporal reason- ~ ing. In Proceedings' of IJCA189, the l lth Joint Conference on Artificzal Intelhgencc, Morgan-Kauf- ~mann, San Mateo, Calif., 1989, pp. 1291 1296 (short version); Exact and approximate reasoning ~about temporal relations. Comput Int. 6, (1990), 132-144 (long version).
• 63: Peter van Beek, Exact and approximate reasoning about qualitative temporal relations, University of Waterloo, Waterloo, Ont., Canada, 1992
• 64: ~VAN BEEK, P. G. 1990b. Reasoning about qualitative temporal information. In Proceedmgs of ~ AAAI-90, the 8th National Conference on Artificial Intelligence, AAAI Press, Menlo Park, Calif., ~ pp. 728-734.
• 65: ~VILAIN, M., AND KAUTZ, H. 1987. Constraint propagation algorithms for temporal reasoning. In ~Proceedings ofAAAI-86. Morgan-Kaufmann, San Mateo, Calif., pp. 377-382.
• 66: Marc Vilain , Henry Kautz , Peter van Beek, Constraint propagation algorithms for temporal reasoning: a revised report, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 67: David L. Waltz, Generating Semantic Descriptions From Drawings of Scenes With Shadows, Massachusetts Institute of Technology, Cambridge, MA, 1972

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Relation systems

General Terms:
Algorithms, Theory

Keywords:
constraint matrices, constraint satisfaction problems, path consistency, relation algebras, relations