More Web Proxy on the site http://driver.im/

research-article

A fast algorithm and datalog inexpressibility for temporal reasoning

Authors:

Manuel Bodirsky,

Jan KáraAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 11, Issue 3

Article No.: 15, Pages 1 - 21

https://doi.org/10.1145/1740582.1740583

Published: 18 May 2010 Publication History

Abstract

We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Bürkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) the constraint satisfaction problem of this language cannot be solved by Datalog or by establishing local consistency.

References

[1]

Allen, J. F. 1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11, 832--843.

Digital Library

[2]

Bodirsky, M. and Dalmau, V. 2006. Datalog and constraint satisfaction with infinite templates. In Proceedings of STACS'06. Springer, Berlin, Germany, 646--659.

Digital Library

[3]

Bodirsky, M. and Dalmau, V. 2008. Datalog and constraint satisfaction with infinite templates (extended abstract). In Proceedings of STACS'06. Full version available arXiv:0809.2386 {cs.LO}.

Digital Library

[4]

Bodirsky, M. and Kára, J. 2008. The complexity of temporal constraint satisfaction problems. In Proceedings of STOC'08. 29--38.

Digital Library

[5]

Bulatov, A., Jeavons, P., and Krokhin, A. 2005. The complexity of constraint satisfaction: An algebraic approach (a survey paper). In Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry, vol. 207. 181--213.

[6]

Bulatov, A., Krokhin, A., and Jeavons, P. G. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720--742.

Digital Library

[7]

Creignou, N., Hermann, M., Krokhin, A., and Salzer, G. 2005. Complexity of clausal constraints over chains. Res. rep. Ecole Polytechnique, Paris-Palaiseau, France.

[8]

Dechter, R. 2003. Constraint Processing. Morgan Kaufmann, San Francisco, CA.

Digital Library

[9]

Diestel, R. 2005. Graph Theory, 3rd Ed. Springer--Verlag, New York, NY.

[10]

Drakengren, T. and Jonsson, P. 1997. Twenty-one large tractable subclasses of Allen's algebra. Artific. Intell. 93, 297--319.

Digital Library

[11]

Duentsch, I. 2005. Relation algebras and their application in temporal and spatial reasoning. Artific. Intell. Rev. 23, 315--357.

Digital Library

[12]

Ebbinghaus, H.-D. and Flum, J. 1999. Finite Model Theory, 2nd ed. Springer, Berlin, Germany.

[13]

Fisher, M., Gabbay, D., and Vila, L. 2005. Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, Amsterdam, The Netherlands.

Digital Library

[14]

Feder, T. and Vardi, M. 1999. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput. 28, 57--104.

Digital Library

[15]

Garey, M. and Johnson, D. 1978. A Guide to NP-Completeness. CSLI Press, Stanford, CA.

[16]

Guttmann, W. and Maucher, M. 2006. Variations on an ordering theme with constraints. In Fourth IFIP International Conference on Theoretical Computer Science (TCS'06), IFIP International Federation for Information Processing 209. 77--90.

[17]

Golumbic, M. C. and Shamir, R. 1993. Complexity and algorithms for reasoning about time: A graph-theoretic approach. J. ACM 40, 5, 1108--1133.

Digital Library

[18]

Hell, P. and Nešetřil, J. 2004. Graphs and Homomorphisms. Oxford University Press, Oxford, U.K.

[19]

Hodges, W. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge, U.K.

Digital Library

[20]

Janson, S., Luczak, T., and Rucinski, A. 2000. Random Graphs. John Wiley and Sons, New York, NY.

[21]

Krokhin, A., Jeavons, P., and Jonsson, P. 2003. Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50, 5, 591--640.

Digital Library

[22]

Koubarakis, M. 2001. Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning. Theoret. Comput. Sci. 266, 311--339.

Digital Library

[23]

Kolaitis, Ph. G. and Vardi, M. Y. 1998. Conjunctive-query containment and constraint satisfaction. In Proceedings of PODS'98. 205--213.

Digital Library

[24]

Ladkin, P. B. and Maddux, R. D. 1994. On binary constraint problems. J. ACM 41, 3, 435--469.

Digital Library

[25]

Marker, D. 2002. Model Theory: An Introduction. Springer, Berlin, Germany.

[26]

Möhring, R. H., Skutella, M., and Stork, F. 2004. Scheduling with and/or precedence constraints. SIAM J. Comput. 33, 2, 393--415.

Digital Library

[27]

Nebel, B. and Bürckert, H.-J. 1995. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. J. ACM 42, 1, 43--66.

Digital Library

[28]

Szendrei, A. 1986. Clones in Universal Algebra. Séminaire de Mathématiques Supérieures. Les Presses de L'Université de Montréal, Montreal, P.Q., Canada.

[29]

van Beek, P. 1992. Reasoning about qualitative temporal information. Artific. Intell. 58, 297--326.

Digital Library

[30]

van der Meyden, R. 1997. The complexity of querying indefinite information about linearly ordered domains. J. Comput. Syst. Sci. 54, 1, 113--135.

Digital Library

[31]

Vilain, M., Kautz, H., and van Beek, P. 1989. Constraint propagation algorithms for temporal reasoning: A revised report. In Reading in Qualitative Reasoning about Physical Systems, Morgan Kaufmann, San Francisco, CA, 373--381.

Digital Library

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Bodirsky MRydval J(2022)On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/356605170:1(1-58)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3566051
Show More Cited By

Index Terms

A fast algorithm and datalog inexpressibility for temporal reasoning
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Datalog and constraint satisfaction with infinite templates

On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite structures. This has applications ...
Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
The complexity of temporal constraint satisfaction problems
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

A temporal constraint language is a set of relations that has a first-order definition in (b Q,<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 11, Issue 3

May 2010

158 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/1740582

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 May 2010

Accepted: 01 February 2009

Received: 01 August 2008

Published in TOCL Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Ministry of Education, Youth and Sports

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
221
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Bodirsky MRydval J(2022)On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/356605170:1(1-58)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3566051
Bodirsky MPakusa WRydval JHermanns HZhang LKobayashi NMiller D(2020)Temporal Constraint Satisfaction Problems in Fixed-Point LogicProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3373718.3394750(237-251)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3373718.3394750
Kramer RMaddux R(2020)Relation algebras of Sugihara, Belnap, Meyer, and ChurchJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2020.100604117(100604)Online publication date: Dec-2020
https://doi.org/10.1016/j.jlamp.2020.100604
Jonsson P(2018)Constants and finite unary relations in qualitative constraint reasoningArtificial Intelligence10.1016/j.artint.2017.12.003257(1-23)Online publication date: Apr-2018
https://doi.org/10.1016/j.artint.2017.12.003
Bodirsky MGreiner J(2018)Complexity of Combinations of Qualitative Constraint Satisfaction ProblemsAutomated Reasoning10.1007/978-3-319-94205-6_18(263-278)Online publication date: 30-Jun-2018
https://doi.org/10.1007/978-3-319-94205-6_18
Hernich ALemos JWolter FSingh SMarkovitch S(2017)Query answering in dl-lite with datatypesProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298407(1142-1148)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298239.3298407
Bodirsky MJonsson P(2017)A model-theoretic view on qualitative constraint reasoningJournal of Artificial Intelligence Research10.5555/3176764.317677358:1(339-385)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3176764.3176773
Bodirsky MPinsker M(2015)Schaefer's Theorem for GraphsJournal of the ACM10.1145/276489962:3(1-52)Online publication date: 30-Jun-2015
https://dl.acm.org/doi/10.1145/2764899
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents