Tractable Set Constraints

Details Tractable Set Constraints Tractable Set Constraints

2011-04-06

arxiv.org/abs/1104.1045v1

Computer Science

Artificial Intelligence

An extended abstract of this paper appears in Proceedings of IJCAI-11

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Tractable Set Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tractable Set Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tractable Set Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-417808