• Sorted by Date • Classified by Publication Type • Sorted by First Author Last Name • Classified by Author Last Name •
L. Chang and Alan K. Mackworth. A Generalization of Generalized Arc Consistency: From Constraint Satisfaction to Constraint-Based Inference. In Proceedings of the IJCAI 2005 Workshop on Modelling and Solving Problems with Constraints, pp. 68–75, Edinburgh, UK, July 2005.
Arc consistency and generalized arc consistency are two of the most important local consistency techniques for binary and non-binary classic constraint satisfaction problems (CSPs). Based on the Semiring CSP and Valued CSP frameworks, arc consistency has also been extended to handle soft constraint satisfaction problems such as fuzzy CSP, probabilistic CSP, max CSP, and weighted CSP. This extension is based on an idempotent or strictly monotonic constraint combination operator. In this paper, we present a weaker condition for applying the generalized arc consistency approach to constraint-based inference problems other than classic and soft CSPs. These problems, including probability inference and maximal likelihood decoding, can be processed using generalized arc consistency enforcing approaches. We also show that, given an additional monotonic condition on the corresponding semiring structure, some of constraintbased inference problems can be approximately preprocessed using generalized arc consistency algorithms.
@InProceedings{IJCAI05,
author = {L. Chang and Alan K. Mackworth},
title = {A Generalization of Generalized Arc Consistency: From Constraint Satisfaction to Constraint-Based Inference},
year = {2005},
month = {July},
booktitle = {Proceedings of the IJCAI 2005 Workshop on Modelling and Solving Problems with Constraints},
address = {Edinburgh, UK},
pages = {68--75},
abstract = {Arc consistency and generalized arc consistency
are two of the most important local consistency
techniques for binary and non-binary classic constraint
satisfaction problems (CSPs). Based on
the Semiring CSP and Valued CSP frameworks,
arc consistency has also been extended to handle
soft constraint satisfaction problems such as fuzzy
CSP, probabilistic CSP, max CSP, and weighted
CSP. This extension is based on an idempotent or
strictly monotonic constraint combination operator.
In this paper, we present a weaker condition for
applying the generalized arc consistency approach
to constraint-based inference problems other than
classic and soft CSPs. These problems, including
probability inference and maximal likelihood decoding,
can be processed using generalized arc consistency
enforcing approaches. We also show that,
given an additional monotonic condition on the corresponding
semiring structure, some of constraintbased
inference problems can be approximately
preprocessed using generalized arc consistency algorithms.},
bib2html_pubtype ={Refereed Conference Proceeding},
bib2html_rescat ={},
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Apr 23, 2014 19:08:34