Title :
Pruning search trees by cylindrical closure
Author :
Lee, J.H.M. ; Van Emden, M.H.
Author_Institution :
Dept. of Comput. Sci., Chinese Univ. of Hong Kong, Hong Kong
Abstract :
Abstract interpretation can be applied to speed up constrained combinatorial search. The approximations used are supersets of the constraints. The authors study an instance of this method by selecting as the supersets the cylindrical closures of Ashby (1964). The result is the method of pruning by cylindrical closure (PCC). When the closures are of order 1 and the constraints are binary, the arc consistency method of Mackworth (1977) is obtained. In the nonbinary case one gets the lookahead inference of CHIP. PCC with closure of order higher than 1 yields new consistency methods
Keywords :
constraint handling; inference mechanisms; scheduling; tree searching; arc consistency method; constrained combinatorial search; cylindrical closures; lookahead inference; search tree pruning; Active appearance model; Artificial intelligence; Automatic programming; Classification tree analysis; Computer science; Logic programming; Processor scheduling; Relaxation methods; Search problems;
Conference_Titel :
Communications, Computers and Signal Processing, 1993., IEEE Pacific Rim Conference on
Conference_Location :
Victoria, BC
Print_ISBN :
0-7803-0971-5
DOI :
10.1109/PACRIM.1993.407252
