An Optimal Data Structure to Handle Dynamic Environment 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 arti0cial 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 ine:cient 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 e:cient solution to the problem (O(lg n) per operation). This is a signi0cant improvement over previously best known ( 3 √ n) 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.