Finite unary relations and qualitative constraint satisfaction
Pages 37 - 45
Abstract
Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an important research direction with important applications. Complexity results for this kind of formalisms have appeared in the literature but they focus on concrete examples and not on general principles. We propose three general methods. The first two methods are based on analysing the given CSP from a model-theoretical perspective, while the third method is based on directly analysing the growth of the representation of solutions. We exemplify our methods on temporal and spatial formalisms including Allen's algebra and RCC5.
References
[1]
Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. In Proc. 26th Annual IEEE Symposium on Logic in Computer Science (LICS-2011), pages 301-310, 2011.
[2]
Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1-3:19, 2014.
[3]
Manuel Bodirsky and M. Grohe. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP-2008), pages 184-196, 2008.
[4]
Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2), 2010.
[5]
Manuel Bodirsky. Cores of countably categorical structures. Logical Methods in Computer Science, 3(1):1-16, 2007.
[6]
Manuel Bodirsky and Hubie Chen. Qualitative temporal and spatial reasoning revisited. J. Log. Comput., 19(6):1359-1383, 2009.
[7]
Manuel Bodirsky and Martin Hils. Tractable set constraints. J. Artif. Intell. Res. (JAIR), 45:731-759, 2012.
[8]
Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. J. Symb. Log., 78(4):1036-1054, 2013.
[9]
Manuel Bodirsky and Stefan Wölfl. RCC8 is polynomial on networks of bounded treewidth. In Proc. 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011), pages 756-761, 2011.
[10]
Andrei Bulatov. Tractable conservative constraint satisfaction problems. In Proceedings of the 18th annual IEEE symposium on logic in computer science, pages 321-???, 2003.
[11]
Andrei Bulatov. Conservative constraint satisfaction re-revisited. Journal of Computer and System Sciences, 82(2):347-356, 2016.
[12]
Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the computational complexity of constraints using finte algebras. SIAM J. Comput., 34(3):720-742, 2005.
[13]
Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005.
[14]
Peter J. Cameron. Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990.
[15]
Georg Cantor. Über unendliche, lineare Punktmannigfaltigkeiten. Mathematische Annalen, 23:453-488, 1884.
[16]
David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis. Building tractable disjunctive constraints. Journal of the ACM, 47(5):826-853, 2000.
[17]
Anthony G. Cohn and Jochen Renz. Qualitative spatial representation and reasoning. In Handbook of Knowledge Representation, pages 551-596. Elsevier, 2008.
[18]
Daniel de Leng and Fredrik Heintz. Qualitative spatio-temporal stream reasoning with unobservable intertemporal spatial relations using landmarks. In Proc. 30th AAAI Conference on Artificial Intelligence (AAAI-2016), pages ...-..., 2016.
[19]
Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artif. Intell., 49:61-95, 1991.
[20]
Thomas Drakengren and Peter Jonsson. Reasoning about set constraints applied to tractable inference in intuitionistic logic. Journal of Logic and Computation, 8(6):855-875, 1998.
[21]
Ivo Düntsch, Hui Wang, and Stephen McCloskey. A relation-algebraic approach to the region connection calculus. Theor. Comput. Sci., 255(1-2):63-83, 2001.
[22]
Stella Giannakopoulou, Charalampos Nikolaou, and Manolis Koubarakis. A reasoner for the RCC-5 and RCC-8 calculi extended with constants. In Proc. 28th AAAI Conference on Artificial Intelligence (AAAI-2014), pages 2659-2665, 2014.
[23]
Pavol Hell and Jaroslav Nešetřil. Graphs and Homomorphisms. Oxford University Press, Oxford, 2004.
[24]
Robin Hirsch. Expressive power and complexity in algebraic logic. Journal of Logic and Computation, 7(3):309-351, 1997.
[25]
Wilfrid Hodges. Model theory. Cambridge University Press, 1993.
[26]
Jinbo Huang. Compactness and its implications for qualitative spatial and temporal reasoning. In Proc. 13th International Conference on Knowledge Representation and Reasoning (KR-2012), 2012.
[27]
Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185-204, 1998.
[28]
Peter Jonsson and Christer Bäckström. A unifying approach to temporal constraint reasoning. Artif. Intell., 102(1):143-155, 1998.
[29]
Peter Jonsson and Thomas Drakengren. A complete classification of tractability in RCC-5. J. Artif. Intell. Res., 6:211-221, 1997.
[30]
Peter Jonsson and Victor Lagerkvist. Upper and lower bounds on the time complexity of infinite-domain CSPs. In Proc. 21st International Conference on Principles and Practice of Constraint Programming (CP-2015), pages 183-199, 2015.
[31]
Markus Junker and Martin Ziegler. The 116 reducts of (ℚ, <, a). J. Symb. Log., 73(3):861-884, 2008.
[32]
Arne Kreutzmann and Diedrich Wolter. Qualitative spatial and temporal reasoning with AND/OR linear programming. In Proc. 21st European Conference on Artificial Intelligence (ECAI-2014, pages 495-500, 2014.
[33]
C. Langford. Some theorems on deducibility. Annals of Mathematics, 28:16-40, 1927.
[34]
Sanjiang Li. On topological consistency and realization. Constraints, 11(1):31-51, 2006.
[35]
Sanjiang Li, Weiming Liu, and Sheng-sheng Wang. Qualitative constraint satisfaction problems: An extended framework with landmarks. Artif. Intell., 201:32-58, 2013.
[36]
Sanjiang Li and Mingsheng Ying. Extensionality of the RCC8 composition table. Fundam. Inform., 55(3-4):363-385, 2003.
[37]
Gérard Ligozat and Jochen Renz. What is a qualitative calculus? A general framework. In Proceedings of PRICAI, pages 53-64, 2004.
[38]
Carsten Lutz and Maja Milicic. A tableau algorithm for description logics with concrete domains and general tboxes. J. Autom. Reasoning, 38(1-3):227-259, 2007.
[39]
Dugald Macpherson. A survey of homogeneous structures. Discrete Mathematics, 311(15):1599-1634, 2011.
[40]
Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. J. ACM, 42(1):43-66, 1995.
[41]
Christos Papadimitriou. On the complexity of integer programming. J. ACM, 28(4):765-768, 1981.
[42]
David A. Randell, Zhan Cui, and Anthony G. Cohn. A spatial logic based on regions and connection. In KR, pages 165-176, 1992.
[43]
Jochen Renz and Bernhard Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell., 108(1-2):69-123, 1999.
[44]
Michael Sioutis and Manolis Koubarakis. Consistency of chordal RCC-8 networks. In Proc. 24th International Conference on Tools with Artificial Intelligence (ICTAI-2012), pages 436-443, 2012.
[45]
Frank Wolter and Michael Zakharyaschev. Spatio-temporal representation and reasoning based on RCC-8. In A. G. Cohn, F. Giunchiglia, and B. Selman, editors, Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning, pages 3-14. Morgan Kaufmann, 2000.
Index Terms
- Finite unary relations and qualitative constraint satisfaction
Recommendations
Constraint satisfaction with succinctly specified relations
The general intractability of the constraint satisfaction problem (CSP) has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint ...
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems
A unary constraint (on the Boolean domain) is a function from {0,1} to the set of real numbers. A free use of auxiliary unary constraints given besides input instances has proven to be useful in establishing a complete classification of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2016
1860 pages
ISBN:9781614996712
Sponsors
- ETINN: Essence ITN Network
- Vrije Universiteit Amsterdam: Vrije Universiteit Amsterdam, Netherlands
- PricewaterhouseCoopers: PricewaterhouseCoopers
- TANDFGROUP: Taylor & Francis Group
Publisher
IOS Press
Netherlands
Publication History
Published: 29 August 2016
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 36Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)1
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in