Constraint satisfaction problems in clausal form

Details Constraint satisfaction problems in clausal form Constraint satisfaction problems in clausal form

2011-03-18

arxiv.org/abs/1103.3693v1

Fundamenta Informaticae, 2011, 109(1): pages 27-81, 83-119

Computer Science

Discrete Mathematics

91 pages, to appear in Fundamenta Informaticae, 2011, as Constraint satisfaction problems in clausal form I: Autarkies and def

Scientific paper

10.3233/FI-2011-428; 10.3233/FI-

This is the report-version of a mini-series of two articles on the foundations of satisfiability of conjunctive normal forms with non-boolean variables, to appear in Fundamenta Informaticae, 2011. These two parts are here bundled in one report, each part yielding a chapter. Generalised conjunctive normal forms are considered, allowing literals of the form "variable not-equal value". The first part sets the foundations for the theory of autarkies, with emphasise on matching autarkies. Main results concern various polynomial time results in dependency on the deficiency. The second part considers translations to boolean clause-sets and irredundancy as well as minimal unsatisfiability. Main results concern classification of minimally unsatisfiable clause-sets and the relations to the hermitian rank of graphs. Both parts contain also discussions of many open problems.

Affiliated with

Also associated with

No associations

Rating

Constraint satisfaction problems in clausal form 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 Constraint satisfaction problems in clausal form, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint satisfaction problems in clausal form will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-186083