Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra

ABSTRACT

Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the constraints are chosen from the full Allen's algebra, this form of satisfiability problem is known to be NP-complete. However, eighteen tractable subalgebras have previously been identified; we show here that these subalgebras include all possible tractable subsets of Allen's algebra. In other words, we show that this algebra contains exactly eighteen maximal tractable subalgebras, and reasoning in any fragment not entirely contained in one of these subalgebras is NP-complete. We obtain this dichotomy result by giving a new uniform description of the known maximal tractable subalgebras, and then systematically using a general algebraic technique for identifying maximal subalgebras with a given property.

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: James F. Allen, Temporal reasoning and planning, Reasoning about plans, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 3: Ola Angelsmark , Peter Jonsson, Some Observations on Durations, Scheduling and Allen's Algebra, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.484-488, September 18-21, 2000
• 4: Frank D. Anger , Rita V. Rodríguez, Effective Scheduling of Tasks under Weak Temporal Interval Constraints, Selected papers from the 5th International Conference on Processing and Management of Uncertainty in Knowledge-Based Systems, Advances in Intelligent Computing, p.584-594, July 04-08, 1994
• 5: A. Belfer , M. C. Golumbic, A combinatorial approach to temporal reasoning, Proceedings of the fifth Jerusalem conference on Information technology, p.774-795, September 1990, Jerusalem, Israel
• 6: P. Bellini , R. Mattolini , P. Nesi, Temporal logics for real-time system specification, ACM Computing Surveys (CSUR), v.32 n.1, p.12-42, March 2000 [doi>10.1145/349194.349197]
• 7: Benzer, S. 1959. On the topology of the genetic fine structure. In Proceedings of the National Academy of Science, U.S.A. vol. 45. 1607--1620.
• 8: Andrei A. Bulatov, A Dichotomy Theorem for Constraints on a Three-Element Set, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.649-658, November 16-19, 2002
• 9: Andrei A. Bulatov , Andrei A. Krokhin , Peter Jeavons, Constraint Satisfaction Problems and Finite Algebras, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.272-282, July 09-15, 2000
• 10: Andrei Bulatov , Andrei Krokhin , Peter Jeavons, The complexity of maximal constraint languages, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.667-674, July 2001, Hersonissos, Greece [doi>10.1145/380752.380868]
• 11: David Cohen , Peter Jeavons , Peter Jonsson , Manolis Koubarakis, Building tractable disjunctive constraints, Journal of the ACM (JACM), v.47 n.5, p.826-853, Sept. 2000 [doi>10.1145/355483.355485]
• 12: Coombs, C., and Smith, J. 1973. On the detection of structures in attitudes and developmental processes. Psych. Rev. 80, 337--351.
• 13: Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 14: Drakengren, T., and Jonsson, P. 1997a. Eight maximal tractable subclasses of Allen's algebra with metric time. J. Artif. Intel. Res. 7, 25--45.
• 15: Thomas Drakengren , Peter Jonsson, Twenty-one large tractable subclasses of Allen's algebra, Artificial Intelligence, v.93 n.1-2, p.297-319, June 1997 [doi>10.1016/S0004-3702(97)00021-0]
• 16: Thomas Drakengren , Peter Jonsson, A complete classification of tractability in Allen's algebra relative to subsets of basic relations, Artificial Intelligence, v.106 n.2, p.205-219, Dec. 1998 [doi>10.1016/S0004-3702(98)00093-9]
• 17: Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: Gavril, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 261--273.
• 20: Gennari, R. 1998. Temporal reasoning and constraint programming---A survey. CWI Quart. 11, 163--214.
• 21: Gerevini, A., and Schubert, L. 1993. Efficient temporal reasoning through timegraphs. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI'93). Morgan Kaufmann, San Mateo, Calif., 648--654.
• 22: Martin Charles Golumbic , Haim Kaplan , Ron Shamir, On the complexity of DNA physical mapping, Advances in Applied Mathematics, v.15 n.3, p.251-261, Sept. 1994 [doi>10.1006/aama.1994.1009]
• 23: Martin Charles Golumbic , Haim Kaplan , Ron Shamir, Graph sandwich problems, Journal of Algorithms, v.19 n.3, p.449-473, Nov. 1995 [doi>10.1006/jagm.1995.1047]
• 24: Martin Charles Golumbic , Ron Shamir, Complexity and algorithms for reasoning about time: a graph-theoretic approach, Journal of the ACM (JACM), v.40 n.5, p.1108-1133, Nov. 1993 [doi>10.1145/174147.169675]
• 25: Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
• 26: Robin Hirsch, Relation algebras of intervals, Artificial Intelligence, v.83 n.2, p.267-295, June 1996 [doi>10.1016/0004-3702(95)00042-9]
• 27: Hirsch, R. 1997. Expressive power and complexity in algebraic logic. J. Logic Comput. 7, 3, 309--351.
• 28: Peter Jonsson , Christer Bäckström, A unifying approach to temporal constraint reasoning, Artificial Intelligence, v.102 n.1, p.143-155, June 1998 [doi>10.1016/S0004-3702(98)00031-9]
• 29: Jonsson, P., and Drakengren, T. 1997. A complete classification of tractability in RCC-5. J. Artif. Intel. Res. 6, 211--221.
• 30: Peter Jonsson , Thomas Drakengren , Christer Bäckström, Computational complexity of relating time points with interval, Artificial Intelligence, v.109 n.1-2, p.273-295, April 1999 [doi>10.1016/S0004-3702(99)00007-7]
• 31: Richard M. Karp, Mapping the genome: some combinatorial problems arising in molecular biology, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.278-285, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167170]
• 32: Kendall, D. 1969. Some problems and methods in statistical archaeology. World Arch. 1, 68--76.
• 33: Manolis Koubarakis, The complexity of query evaluation in indefinite temporal constraint databases, Theoretical Computer Science, v.171 n.1-2, p.25-60, Jan. 15, 1997
• 34: Manolis Koubarakis, Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning, Theoretical Computer Science, v.266 n.1-2, p.311-339, 09/06/2001 [doi>10.1016/S0304-3975(00)00177-8]
• 35: Manolis Koubarakis , Spiros Skiadopoulos, Querying temporal and spatial constraint networks in PTIME, Artificial Intelligence, v.123 n.1-2, p.223-263, Oct. 2000 [doi>10.1016/S0004-3702(00)00055-2]
• 36: Andrei A. Krokhin , Peter Jeavons , Peter Jonsson, The Complexity of Constraints on Intervals and Lengths, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.443-454, March 14-16, 2002
• 37: Andrei Krokhin , Peter Jonsson, Extending the Point Algebra into the Qualitative Algebra, Proceedings of the Ninth International Symposium on Temporal Representation and Reasoning (TIME'02), p.28, July 07-09, 2002
• 38: Peter B. Ladkin , Roger D. Maddux, On binary constraint problems, Journal of the ACM (JACM), v.41 n.3, p.435-469, May 1994 [doi>10.1145/176584.176585]
• 39: Peter B. Ladkin , Alexander Reinefeld, Fast algebraic methods for interval constraint problems, Annals of Mathematics and Artificial Intelligence, v.19 n.3-4, p.383-411, 1997 [doi>10.1023/A:1018968024833]
• 40: Ligozat, G. 1996. A new proof of tractability for ORD-Horn relations. In Proceedings of the 13th National (US) Conference on Artificial Intelligence (AAAI-96). AAAI Press, Menlo Park, Calif., 395--401.
• 41: Gérard Ligozat, ’’Corner‘‘ Relations in Allen‘s algebra, Constraints, v.3 n.2-3, p.165-177, June 1998 [doi>10.1023/A:1009721626239]
• 42: Itay Meiri, Combining qualitative and quantitative constraints in temporal reasoning, Artificial Intelligence, v.87 n.1-2, p.343-385, Nov. 1996 [doi>10.1016/0004-3702(95)00109-3]
• 43: Nebel, B. 1997a. Archive of C-programs used for obtaining the results from {Nebel 1997b}. Available from the author at http://www.informatik.uni-freiburg.de/˜nebel/journals.html.
• 44: Nebel, B. 1997b. Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class. Constraints 1, 3, 175--190.
• 45: Bernhard Nebel , Hans-Jürgen Bürckert, Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra, Journal of the ACM (JACM), v.42 n.1, p.43-66, Jan. 1995 [doi>10.1145/200836.200848]
• 46: Klaus Nökel, Temporally distributed symptoms in technical diagnosis, Springer-Verlag New York, Inc., New York, NY, 1991
• 47: Opatrný, J. 1979. Total ordering problem. SIAM J. Comput. 8, 1, 111--114.
• 48: Papadimitriou, C., and Yannakakis, M. 1979. Scheduling interval ordered tasks. SIAM J. Comput. 8, 3, 405--409.
• 49: Itsik Pe'er , Ron Shamir, Satisfiability problems on intervals and unit intervals, Theoretical Computer Science, v.175 n.2, p.349-372, April 10, 1997
• 50: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 51: Eddie Schwalb , Lluís Vila, Temporal Constraints: A Survey, Constraints, v.3 n.2-3, p.129-149, June 1998 [doi>10.1023/A:1009717525330]
• 52: Song, F., and Cohen, R. 1988. The interpretation of temporal relations in narrative. In Proceedings of the 7th National (US) Conference on Artificial Intelligence. AAAI Press/The MIT Press, St. Paul, Minn., USA, 745--750.
• 53: Kostas Stergiou , Manolis Koubarakis, Backtracking algorithms for disjunctions of temporal constraints, Artificial Intelligence, v.120 n.1, p.81-117, June 2000 [doi>10.1016/S0004-3702(00)00019-9]
• 54: Szendrei, A. 1995. Maximal non-affine reducts of simple affine algebras. Algebra Univ. 34, 1, 144--174.
• 55: Tarski, A. 1941. On the calculus of relations. J. Symb. Logic 6, 73--89.
• 56: Peter van Beek, Reasoning about qualitative temporal information, Artificial Intelligence, v.58 n.1-3, p.297-326, Dec. 1992 [doi>10.1016/0004-3702(92)90011-L]
• 57: Peter van Beek , Robin Cohen, Exact and approximate reasoning about temporal relations, Computational Intelligence, v.6 n.3, p.132-147, Aug. 1990 [doi>10.1111/j.1467-8640.1990.tb00130.x]
• 58: van Beek, P., and Manchak, D. 1996. The design and experimental analysis of algorithms for temporal reasoning. J. Artif. Intel. Res. 4, 1--18.
• 59: Vilain, M. 1982. A system for reasoning about time. In Proceedings of the 2nd National (US) Conference on Artificial Intelligence (Pittsburgh, Pa.), AAAI Press, 197--201.
• 60: 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
• 61: Stephen A. Ward , Robert H. Halstead, Jr., Computation structures, MIT Press, Cambridge, MA, 1990
• 62: Wilson, R. 1999. The maximal subgroups of the Baby Monster. I. J. Algebra 211, 1, 1--14.
• 63: Yang, X. 2000. A classification of maximal subsemigroups of finite order-preserving transformation semigroups. Commun. Algebra 28, 3, 1503--1513.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

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

General Terms:
Algorithms, Theory

Keywords:
Allen's algebra, NP-completeness, complexity, dichotomy theorem, representing graphs by intervals, satisfiability of temporal constraints, tractable cases