Balancing Execution Trees∗

Algorithmic debugging is a debugging tech-nique that uses a data structure represent-ing all computations of a program. This data structure is the so-called Execution Tree and it strongly influences on the performance of the technique. In this work we present a transfor-mation that allows us to automatically balance execution trees by collapsing and projecting some strategic nodes. We prove that the trans-formation is sound in the sense that all the bugs found after the transformation are real bugs; and if at least one bug is detectable be-fore the transformation, then at least one bug will be also detectable after the transforma-tion. We have implemented the technique and performed several experiments with real appli-cations. The experimental results confirm the usefulness of the technique.