Alan K. Mackworth's Publications

Sorted by DateClassified by Publication TypeSorted by First Author Last NameClassified by Author Last Name

A Generalization of Generalized Arc Consistency: From Constraint Satisfaction to Constraint-Based Inference

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.

Download

[PDF]157.9kB  

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.

BibTeX

@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