{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19083"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19083","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Improvement of constrained searches","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gooley, Markian Myron"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Wah, Benjamin W."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T11:56:25Z","date_published":"2011-05-07T11:56:25Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Gooley, Markian Myron"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210817","(UMI)AAI9210817"],"render_values":[{"text":"AAI9210817","href":null,"code":true},{"text":"(UMI)AAI9210817","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19083","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wah, Benjamin W."]},{"key":"dc:creator","label":"Author","values":["Gooley, Markian Myron"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T11:56:25Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Gooley, Markian Myron"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210817","(UMI)AAI9210817","http://hdl.handle.net/2142/19083"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T11:56:25Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210817.pdf: 5760971 bytes, checksum: 92c9540cedae6ee5e6755f9b75e0209e (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:15-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Improvement of constrained searches"]}]}],"canonical_facts":{"dc:contributor":["Wah, Benjamin W."],"dc:creator":["Gooley, Markian Myron"],"dc:date":["2011-05-07T11:56:25Z","10000-01-01","1991"],"dc:description":["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.","Made available in DSpace on 2011-05-07T11:56:25Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210817.pdf: 5760971 bytes, checksum: 92c9540cedae6ee5e6755f9b75e0209e (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:15-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9210817","(UMI)AAI9210817","http://hdl.handle.net/2142/19083"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Gooley, Markian Myron"],"dc:subject":["Computer Science"],"dc:title":["Improvement of constrained searches"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}