Complete algorithms for constraint solving typically exploit properties like (in)consistency or interchangeability, which they detect by means of incomplete yet effective algorithms and use to reduce the search space. In this paper, we study a wide range of properties which includes most of the ones used by existing CSP algorithms as well as some which have not yet been considered in the literature, and we investigate their use in CSP solving. We clarify the relationships between these notions and characterise the complexity of the problem of checking them. Following the CSP approach, we then determine a number of relaxations (for instance local versions) which provide sufficient conditions whose detection is tractable. This work is a first step towards a comprehensive framework for CSP properties, and it also shows that new notions still remain to be exploited.

Exploiting fixable, removable, and implied values in Constraint Satisfaction Problems / L., Bordeaux; Cadoli, Marco; Mancini, Toni. - STAMPA. - 3452:(2004), pp. 270-284. (Intervento presentato al convegno Eleventh International Conference on Logic for Programming, Artificial Intelligence and Reasoning tenutosi a Montevideo, Uruguay nel March 14-18, 2005) [10.1007/978-3-540-32275-7_19].

Exploiting fixable, removable, and implied values in Constraint Satisfaction Problems

CADOLI, Marco;MANCINI, Toni
2004

Abstract

Complete algorithms for constraint solving typically exploit properties like (in)consistency or interchangeability, which they detect by means of incomplete yet effective algorithms and use to reduce the search space. In this paper, we study a wide range of properties which includes most of the ones used by existing CSP algorithms as well as some which have not yet been considered in the literature, and we investigate their use in CSP solving. We clarify the relationships between these notions and characterise the complexity of the problem of checking them. Following the CSP approach, we then determine a number of relaxations (for instance local versions) which provide sufficient conditions whose detection is tractable. This work is a first step towards a comprehensive framework for CSP properties, and it also shows that new notions still remain to be exploited.
2004
Eleventh International Conference on Logic for Programming, Artificial Intelligence and Reasoning
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Exploiting fixable, removable, and implied values in Constraint Satisfaction Problems / L., Bordeaux; Cadoli, Marco; Mancini, Toni. - STAMPA. - 3452:(2004), pp. 270-284. (Intervento presentato al convegno Eleventh International Conference on Logic for Programming, Artificial Intelligence and Reasoning tenutosi a Montevideo, Uruguay nel March 14-18, 2005) [10.1007/978-3-540-32275-7_19].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/210132
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 2
social impact