Data Structures and Algorithms

One More Step Towards Generalized Graph-Based Weakly Relational Domains

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