Home |
Personal Info |
Papers |
Teaching |
Links |
Factorizing Equivalent Variable Pairs in ROBDD-Based Implementations of Pos
Roberto Bagnara
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma
Italy
Peter Schachte
Department of Computer Science
The University of Melbourne
Parkville, Victoria 3052
Australia
Abstract:
The subject of groundness analysis for (constraint) logic programs has been widely studied, and interesting domains have been proposed. Pos has been recognized as the most suitable domain for capturing the kind of dependencies arising in groundness analysis, and Reduced Ordered Binary Decision Diagrams (ROBDDs) are generally accepted to be the most efficient representation for Pos. Unfortunately, the size of an ROBDDs is, in the worst case, exponential in the number of variables it depends upon. Earlier work [1] has shown that a hybrid representation that separates the definite information from the dependency information is considerably more efficient than keeping the two together. The aim of the present paper is to push this idea further, also separating out certain dependency information, in particular all pairs of variables that are always either both ground or neither ground. We find that this new hybrid representation is a significant improvement over previous work.References
- 1
-
R. Bagnara.
A reactive implementation of Pos using ROBDDs.
In H. Kuchen and S. D. Swierstra, editors, Programming Languages: Implementations, Logics and Programs, Proceedings of the Eighth International Symposium, volume 1140 of Lecture Notes in Computer Science, pages 107-121, Aachen, Germany, 1996. Springer-Verlag, Berlin.
Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.
[Page last updated on January 22, 2000, 17:04:53.]
bagnara@cs.unipr.it
Home | Personal | Papers | Teaching | Links