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 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.

Factorizing Equivalent Variable Pairs in ROBDD-Based Implementations of <EM>Pos</EM> / BAGNARA R.; SCHACHTE P.. - 1548 of LNCS(1999), pp. 471-485. ((Intervento presentato al convegno 7th International Conference on Algebraic Methodology and Software Technology tenutosi a Amazonia, Brasil nel January 4-8, 1999.

Factorizing Equivalent Variable Pairs in ROBDD-Based Implementations of Pos

BAGNARA, Roberto;
1999

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 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.
9783540654629
Factorizing Equivalent Variable Pairs in ROBDD-Based Implementations of <EM>Pos</EM> / BAGNARA R.; SCHACHTE P.. - 1548 of LNCS(1999), pp. 471-485. ((Intervento presentato al convegno 7th International Conference on Algebraic Methodology and Software Technology tenutosi a Amazonia, Brasil nel January 4-8, 1999.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11381/1448224
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 18
social impact