Beyond Consistency and SubstitutabilityReportar como inadecuado

Beyond Consistency and Substitutability - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 IRIT - Institut de recherche en informatique de Toulouse

Abstract : Elimination of inconsistent values in instances of the constraint satisfaction problem CSP conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values which are neither inconsistent nor substitutable can also be deleted while conserving at least one solution. This allows us to state novel rules for the elimination of values in binary CSP. From a practical point of view, we show that one such rule can be applied in the same asymptotic time complexity as neighbourhood substitution but is strictly stronger. An alternative to the elimination of values from domains is the elimination of variables. We give novel satisfiability-preserving variable elimination operations. In each case we show that if the instance is satisfiable, then a solution to the original instance can always be recovered in low-order polynomial time from a solution to the reduced instance.

Keywords : Neighbourhood substitution Pattern Binary CSP Value elimination Variable elimination

Autor: Martin C. Cooper -



Documentos relacionados