An optimal data structure to handle dynamic environments in non-deterministic computations

摘要

The single most serious issue in the development of a parallel implementation of non-deterministic programming languages and systems (e.g., logic programming, constraint programming, search-based artificial intelligence systems) is the dynamic management of the binding environments―i.e., the ability to associate with each parallel computation the correct set of bindings/values representing the solution generated by that particular branch of the non-deterministic computation. The problem has been abstracted and formally studied previously (ACM Trans. Program. Lang. Syst. 15(4) (1993) 659; New Generation Comput. 17(3) (1999) 285), but to date only relatively inefficient data structures (ACM Trans. Program. Lang. Syst. (2002); New Generation Comput. 17(3) (1999) 285; J. Funct. Logic Program. Special issue #1 (1999)) have been developed to solve it. We provide a very efficient solution to the problem (O(1g n) per operation). This is a significant improvement over previously best known Ω(n~(1/3)) solution. Our solution is provably optimal for the pointer machine model. We also show how the solution can be extended to handle the abstraction of search problems in object-oriented systems, with the same time complexity.