Tractable Set Constraints

Bodirsky, Manuel; Hils, Martin; Krimkevitch, Alex

doi:10.5591/978-1-57735-516-8/IJCAI11-093

Tractable Set Constraints

Manuel Bodirsky, Martin Hils, Alex Krimkevitch

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 510-514.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-093

Abstract

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

Manuel Bodirsky, Martin Hils, and Alex Krimkevitch. 2011. Tractable Set Constraints. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 510–514. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-093

@inproceedings{ijcai2011p93,
  title     = {Tractable Set Constraints},
  author    = {Bodirsky, Manuel and Hils, Martin and Krimkevitch, Alex},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {510--514},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-093},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-093},
}

TY  - CPAPER
TI  - Tractable Set Constraints
AU  - Bodirsky, Manuel
AU  - Hils, Martin
AU  - Krimkevitch, Alex
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 510
EP  - 514
DO  - 10.5591/978-1-57735-516-8/IJCAI11-093
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-093
ER  -