CS Seminar: Alessandro Dal Palù, November 27, 2002

Speaker: Alessandro Dal Palù,
Dipartimento di Matematica e Informatica, Università di Udine, Italy.
Date and Time: Wednesday, November 27, 2002 at 15:00
Place: Sala Riunioni,
Dipartimento di Matematica, Università di Parma, Via D'Azeglio 85/A, I-43100 Parma
Title: An Optimal Data Structure to Handle Dynamic Environments in Non-Deterministic Computations
Abstract: 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 AI 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, but to date only relatively inefficient data structures have been developed to solve it. We provide a very efficient solution to the problem ( $O(\lg n)$ per operation). This is a significant improvement over previously best known $\Omega(\sqrt[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.
Contact Person: Gianfranco Rossi

[Page last updated on November 20, 2002, 10:00:11.]

Page maintained by
Enea Zaffanella