Roberto, Margherita and Beatrice


Personal Info




Boolean Functions for Finite-Tree Dependencies (TR)

Roberto Bagnara
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma

Enea Zaffanella
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma

Roberta Gori
Dipartimento di Informatica
Università di Pisa
Corso Italia 40
I-56125 Pisa

Patricia M. Hill
School of Computing
University of Leeds
Leeds, LS2 9JT
United Kingdom


Several logic-based languages, such as Prolog II and its successors, SICStus Prolog and Oz, offer a computation domain including rational trees. Infinite rational trees allow for increased expressivity (cyclic terms can provide efficient representations of grammars and other useful objects) and for faster unification (due to the safe omission of the occurs-check). Unfortunately, the use of infinite rational trees has problems. For instance, many of the built-in and library predicates are ill-defined for such trees and need to be supplemented by run-time checks whose cost may be significant. In a companion paper [3] we have proposed a data-flow analysis aimed at the knowledge of those program variables (the finite variables) that will always be bound to finite terms. The analysis domain introduced in [3] correctly captures the creation and propagation of cyclic terms, but is not capable of propagating the guarantees of finiteness that come from built-in predicates and program annotations. Here we present a domain of Boolean functions that precisely captures how the finiteness of some variables influences the finiteness of other variables. This domain of finite-tree dependencies provides relational information that is important for the precision of the overall finiteness analysis. It also combines obvious similarities, interesting differences and somewhat unexpected connections with classical domains for groundness dependencies.


R. Bagnara, R. Gori, P. M. Hill, and E. Zaffanella.
Finite-Tree Analysis for Constraint Logic-Based Languages.
Quaderno 251, Dipartimento di Matematica, Università di Parma, 2001.

Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.

[Page last updated on February 28, 2003, 17:44:23.]

© Roberto Bagnara

Home | Personal | Papers | Teaching | Links