Computer Science – Logic in Computer Science
Scientific paper
2008-05-21
Computer Science
Logic in Computer Science
15 pages
Scientific paper
We investigate the applicability of divisible residuated lattices (DRLs) as a general evaluation framework for soft constraint satisfaction problems (soft CSPs). DRLs are in fact natural candidates for this role, since they form the algebraic semantics of a large family of substructural and fuzzy logics. We present the following results. (i) We show that DRLs subsume important valuation structures for soft constraints, such as commutative idempotent semirings and fair valuation structures, in the sense that the last two are members of certain subvarieties of DRLs (namely, Heyting algebras and BL-algebras respectively). (ii) In the spirit of previous work of J. Larrosa and T. Schiex [2004], and S. Bistarelli and F. Gadducci [2006] we describe a polynomial-time algorithm that enforces k-hyperarc consistency on soft CSPs evaluated over DRLs. Observed that, in general, DRLs are neither idempotent nor totally ordered, this algorithm amounts to a generalization of the available algorithms that enforce k-hyperarc consistency.
No associations
LandOfFree
k-Hyperarc Consistency for Soft Constraints over Divisible Residuated Lattices 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 k-Hyperarc Consistency for Soft Constraints over Divisible Residuated Lattices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-Hyperarc Consistency for Soft Constraints over Divisible Residuated Lattices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-290204