On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems
From Tetherless World Wiki
(Redirected from DBLP:conf/aaai/ChoueiryN98)
Citation: Berthe Y. Choueiry and Guevara Noubir. (1998) On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems. In Knowledge Systems, AI Laboratory, October,1998.
| Publication inproceedings ( Edit ) | |
| type | InProceedings |
| bibtype | inproceedings |
| Bibtex basics | |
| author | Berthe Y. Choueiry and Guevara Noubir |
| title | On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems |
| booktitle | Knowledge Systems, AI Laboratory |
| address | Stanford, CA, USA |
| year | 1998 |
| month | October |
| Bibtex more | |
| note | A previous version of this paper appeared in the Proceedings of AAAI'98. |
| Access Paper | |
| abstract | In AAAI'91 paper, Freuder defines several types of interchangeability to capture the equivalence among the values of a variable in a discrete constraint satisfaction problem (CSP), and provides a procedure for computing one type of local interchangeability. In this paper, we first extend this procedure for computing a weak form of local interchangeability. Second, we show that the modified procedure can be used to generate a conjunctive decomposition of the CSP by localizing, in the CSP, independent subproblems. Third, for the case of constraints of mutual exclusion, we show that locally interchangeable values can be computed in a straightforward manner, and that the only possible type of local interchangeability is the one that induces locally independent subproblems. Finally, we give hints on how to exploit these results in practice, establish a lattice that relates some types of interchangeability, and identify directions for future research. |
| KSL Technical Report ID: KSL-98-24 |
Facts about On the Computation of Local Interchangeability in Discrete Constraint Satisfaction ProblemsRDF feed
| Abstract | In AAAI'91 paper, Freuder defines several … In AAAI'91 paper, Freuder defines several types of interchangeability to capture the equivalence among the values of a variable in a discrete constraint satisfaction problem (CSP), and provides a procedure for computing one type of local interchangeability. In this paper, we first extend this procedure for computing a weak form of local interchangeability. Second, we show that the modified procedure can be used to generate a conjunctive decomposition of the CSP by localizing, in the CSP, independent subproblems. Third, for the case of constraints of mutual exclusion, we show that locally interchangeable values can be computed in a straightforward manner, and that the only possible type of local interchangeability is the one that induces locally independent subproblems. Finally, we give hints on how to exploit these results in practice, establish a lattice that relates some types of interchangeability, and identify directions for future research. d identify directions for future research. |
| Address | Stanford, CA, USA + |
| Author | Berthe Y. Choueiry and Guevara Noubir + |
| Bibtype | inproceedings + |
| Booktitle | Knowledge Systems, AI Laboratory + |
| Has author | Berthe Y. Choueiry and Guevara Noubir + |
| Has identifier | KSL-98-24 + |
| Has publishing details | October,1998 + |
| Has title | On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems + |
| Has where published | Knowledge Systems, AI Laboratory + |
| Has year | 1998 + |
| Ksl tr id | KSL-98-24 + |
| Month | October + |
| Note | A previous version of this paper appeared in the Proceedings of AAAI'98. |
| Process note | NO + |
| Title | On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems + |
| Year | 1998 + |
