Andorra Model Revised: Introducing Nested Domain Variables and a Targeted Search

R Yang, S Gregory

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

The Andorra Model is a computation model to improve the efficiency of Prolog programs as well as to exploit parallelism. The model was designed in two stages: the basic model and the extended model. The major difference between the two is that a binding determinacy principle replaced the original clause determinacy principle, and an and-or box rewriting computation replaced the traditional resolution. This work aims to tackle some unsolved problems left in the Extended Andorra Model. We propose to replace the original and-or box rewriting method by a targeted search. The search is called targeted because we only look for possible solutions of certain specified variables. The variables shared between different local computations can be dynamically changed to finite domain variables after the targeted search, and their consistency checked eagerly. Therefore, many unnecessary or-branches can be pruned at an early stage. A special feature of our domain variable is that we allow a domain to contain non-ground compound terms, i.e., open structures. Variables within these open structures can also become domain variables, leading to nested domain variables. We have tested our idea by an experimental implementation under SICStus Prolog, and obtained very encouraging results.
Translated title of the contributionAndorra Model Revised: Introducing Nested Domain Variables and a Targeted Search
Original languageEnglish
Title of host publication8th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2001, Havana, 3-7 December
EditorsR Nieuwenhuis, A Voronkov
PublisherSpringer
Pages610 - 623
Number of pages14
ISBN (Print)3540429573
Publication statusPublished - Dec 2001

Bibliographical note

Other: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000287. Lecture Notes in Computer Science 2250

Cite this

Yang, R., & Gregory, S. (2001). Andorra Model Revised: Introducing Nested Domain Variables and a Targeted Search. In R. Nieuwenhuis, & A. Voronkov (Eds.), 8th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2001, Havana, 3-7 December (pp. 610 - 623). Springer. http://www.springerlink.com/content/0w5mmhyqkl8qgdtp/