Improvement of constrained searches

Search is ubiquitous in computer science, but most searches are performed under constraints: time, memory, dependences. We study several cases of constrained search and present methods for improving their performance. Execution of Prolog programs amounts to a search with several types of dependences. We present a method for static reordering of goals in Prolog clauses, characterizing the degrees of equivalence between the original and reordered code, characterizing restrictions on reordering, presenting a heuristic for choosing amongst permissible reorderings, and showing how to restore equivalence that might be lost in the reordering process. Heuristic search in restricted memory is another constrained search. We present a new method called speculative search which is competitive with other searches used when memory is limited.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Gooley, Markian Myron

Contributors dc:contributor

• Wah, Benjamin W.

• Computer Science

Statement dc:rights

• Copyright 1991 Gooley, Markian Myron

Language dc:language

eng

Identifier

AAI9210817
(UMI)AAI9210817

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/19083