Authors: Sven de Smet
Comments: 21 pages. This paper is a slightly modified version of a draft paper that was submitted to ParCo 2011 and is very preliminary. Since I do not have the resources to complete this paper by increasing its clarity, adding examples, adding an experimental evaluation and adding a section on related work, I'm making it available so that it may be useful to others.
This paper proposes to extend graph-based weakly relational domains
to a generalized relational context. Using a new definition of coherence, we show
that the definition of a normal form for this domain is simplified. A transitive closure
algorithm for combined relations is constructed and a proof of its correctness
is given. Using the observed similarity between transitive closure of a combined
relation and the normal form closure of a graph-based weakly relational domain,
we extract a mathematical property that a relational abstract domain must satisfy in
order to allow us to use an algorithm with the same form as the transitive closure
algorithm to compute the normal form of a graph-based weakly relational domain.
Category: Data Structures and Algorithms