Skip to Main content Skip to Navigation
Reports

From Implicit to Explicit Pavings

Gilles Chabert 1 Rémi Douence 2
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
2 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : A combinatorial search can either be performed by using an implicit search tree, where an initial state is recursively transformed until some goal state is reached, or by using an explicit search tree, where an initial tree structure containing the root state is iteratively expanded until the leaves match the set of goal states. This paper proposes an exploratory study aimed at showing that explicit search trees can play a distinguished role in the field of numerical constraints. The first advantage of an explicit search is expressiveness: we can write new algorithms or reformulate existing ones in a simple and unified way. The second advantage is efficiency, since an implicit search may also lead to a blowup of redundant computations. This is illustrated through various examples.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00720739
Contributor : Gilles Chabert <>
Submitted on : Wednesday, July 25, 2012 - 3:32:34 PM
Last modification on : Thursday, March 5, 2020 - 5:47:39 PM
Long-term archiving on: : Friday, December 16, 2016 - 2:53:04 AM

File

RR-8028.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00720739, version 1

Citation

Gilles Chabert, Rémi Douence. From Implicit to Explicit Pavings. [Research Report] RR-8028, INRIA. 2012. ⟨hal-00720739⟩

Share

Metrics

Record views

537

Files downloads

199