|
Factorizing Equivalent Variable Pairs in ROBDD-Based Implementations of Pos
Roberto Bagnara
Peter Schachte
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
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 |