Faster Algorithms for Algebraic Path Properties in RSMs with
Constant Treewidth∗
Krishnendu Chatterjee†1 , Rasmus Ibsen-Jensen‡1 , Andreas Pavlogiannis§1 , and
Prateesh Goyal¶2
1

arXiv:1410.7724v2 [cs.PL] 25 Nov 2014

2

IST Austria (Institute of Science and Technology Austria)
IIT Bombay (Indian Institute of Technology Bombay) Mumbai, India
November 27, 2014
Abstract

Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias
analysis, constant propagation, etc. Recursive state machines (RSMs) are standard models for interprocedural
analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring, and
path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, etc. The
traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the
entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in a very important algorithmic
distinction between the resource usage of the one-time preprocessing vs for each individual query. The second
aspect that we consider is that the control flow graphs for most programs have constant treewidth.
Our main contributions are simple and implementable algorithms that support multiple queries for algebraic
path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have
small additional one-time preprocessing, but can answer subsequent queries significantly faster as compared to
the current best-known solutions for several important problems, such as interprocedural reachability and shortest
path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path
that gives a significant speed-up on several benchmarks.

1 Introduction
Interprocedural analysis and RSMs. Interprocedural analysis is one of the classic algorithmic problem in programming languages which is at the heart of numerous applications, ranging from alias analysis, to data dependencies
(modification and reference side effect), to constant propagation, to live and use analysis [1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12]. In seminal works [1, 2] it was shown that a large class of interprocedural dataflow analysis problems can be solved in polynomial time. A standard model for interprocedural analysis is recursive state machines
(RSMs) [13] (aka supergraph in [1]). A RSM is a formal model for control flow graphs of programs with recursion.
We consider RSMs that consist of component state machines (CSMs), one for each method that has a unique entry
and unique exit, and each CSM contains boxes which are labeled as CSMs that allows calls to other methods.
Algebraic path properties. To specify properties of traces of a RSM we consider a very general framework, where
edges of the RSM are labeled from a partially complete semiring (which subsumes bounded and finite distributive
semirings), and we refer to the labels of the edges as weights. For a given path, the weight of the path is the
∗ This work has been supported by the Austrian Science Foundation (FWF) under the NFN RiSE (S11405-07), FWF Grant P23499-N23,
ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.
† krish.chat@ist.ac.at
‡ ribsen@ist.ac.at
§ pavlogiannis@ist.ac.at
¶ prateesh@iitb.ac.in

1

Our
Results

Preprocessing time
O(log n · (n + h · b))
O(log n · (n + h · b))

Space
O(n · log n)
O(n)

Single source query
O(n)
O(n)

Pair query
O(1)
O(log n)

Reference
Theorem 3
Theorem 3

Table 1: Interprocedural same-context algebraic path problem on RSMs with b boxes and constant treewidth, for
stack height h.
semiring product of the weights on the edges of the path, and to choose among different paths we use the semiring
plus operator. For example, (i) with Boolean semiring (with semiring product as AND, and semiring plus as OR)
we can express the reachability property; (ii) with tropical semiring (with real-edge weights, semiring product as
standard sum, and semiring plus as minimum) we can express the shortest path property; and (iii) with Viterbi
semiring (with probability value on edges, semiring product as standard multiplication and semiring plus as maximum) we can express the most probable path property. The algebraic path properties expressed in our framework
subsumes the IFDS/IDE frameworks [1, 2] which consider finite semirings and meet over all paths as the semiring
plus operator. Since IFDS/IDE are subsumed in our framework, the large and important class of dataflow analysis
problems that can be expressed in IFDS/IDE frameworks can also be expressed in our framework.
Two important aspects. In the traditional algorithms for interprocedural analysis, the starting point is typically
fixed as the entry point of a specific method. In graph theoretic parlance, graph algorithms can consider two types
of queries: (i) a pair query that given nodes u and v (called (u, v)-pair query) asks for the algebraic path property
from u to v; and (ii) a single-source query that given a node u asks for the answer of (u, v)-pair queries for all
nodes v. Thus the traditional algorithms for interprocedural analysis has focused on the answer for one singlesource query. Moreover, the existing algorithms also consider that the input control flow graph is arbitrary, and
do not exploit the fact that most control flow graphs satisfy several elegant structural properties. In this work, we
consider two new aspects, namely, (i) multiple pair and single-source queries, and (ii) exploit the fact that typically
the control flow graphs of programs satisfy an important structural property called the constant treewidth property.
We describe in details the two aspects.
• Multiple queries. We first describe the relevance of pair and multiple pair queries, and then the significance
of even multiple single-source queries. In alias analysis, the question is whether two pointers may point to
the same object, which is by definition modeled as a question between a pair of nodes. Similarly, e.g., in
constant propagation, given a function call, a relevant question is whether some variable remains constant
within the entry and exit of the function (in general it can be between a pair of nodes of the program). This
shows that the pair query problem, and the multiple pair queries are relevant in many applications. Finally,
consider a run-time optimization scenario, where the goal is to decide whether a variable remains constant
from now on, and this corresponds to a single-source query, where the starting point is the current execution
point of the program. Thus multiple pair queries and multiple single-source queries are relevant for several
important static analysis problems.
• Constant treewidth. A very well-known concept in graph theory is the notion of treewidth of a graph, which
is a measure of how similar a graph is to a tree (a graph has treewidth 1 precisely if it is a tree) [14]. The
treewidth of a graph is defined based on a tree decomposition of the graph [15], see Section 2 for a formal
definition. Beyond the mathematical elegance of the treewidth property for graphs, there are many classes of
graphs which arise in practice and have constant treewidth. The most important example is that the control
flow graph for goto-free programs for many programming languages are of constant treewidth [16], and it
was also shown in [17] that typically all Java programs have constant treewidth. An important property of
constant-treewidth graphs is that the number of edges is at most a constant factor larger than the number of
nodes. This has been considered in the comparison Tables 2 and 3.
Our contributions. In this work we consider RSMs where every CSM has constant treewidth, and the algorithmic
question of answering multiple single-source and multiple pair queries, where each query is a same-context query
(a same-context query starts and ends with an empty stack, see [20] for the significance of same-context queries).
In the analysis of multiple queries, there is a very important algorithmic distinction between one-time preprocessing (denoted as the preprocessing time), and the work done for each individual query (denoted as the query time).
There are two end-points in the spectrum of tradeoff between the preprocessing and query resources that can be
obtained by using the classical algorithms for one single-source query, namely, (i) the complete preprocessing, and
(ii) the no preprocessing. In complete preprocessing, the single-source answer is precomputed with every node
as the starting point (for example, in graph reachability this corresponds to computing the all-pairs reachability
2

IDE/IFDS
(complete preprocessing)
IDE/IFDS
(no preprocessing)
Our
Results

Preprocessing time
O(n2 · |D|3 )

Space
O(n2 · |D|)

Single source query
O(n · |D|)

Pair query
O(|D|)

Reference
[1, 2]

-

O(n · |D|)

O(n · |D|3 )

O(n · |D|3 )

[1, 2]

2

O(|D| · log n · (n + b · |D|))
O(n · |D|2 + log n · (b · |D|3 + n))

2

O(n · log n · |D| )
O(n · |D|2 )

2

O(n · |D| )
O(n · |D|2 )

2

O(|D| )
O(log n · |D|2 )

Corollary 1
Corollary 1

Table 2: Interprocedural same-context algebraic path problem on RSMs with b boxes and constant treewidth,
where the semiring is over the subset of |D| elements and the plus operator is the meet operator of the IFDS
framework. The special case of reachability is obtained when |D| = 1.

GPR (complete preprocessing)
GPR (no preprocessing)
Our
Results

Preprocessing time
O(n5 )
O(n2 · log n)
O(n2 · log n)

Space
O(n2 )
O(n)
O(n · log n)
O(n)

Single-source query
O(n)
O(n4 )
O(n)
O(n)

Pair query
O(1)
O(n4 )
O(1)
O(log n)

Reference
[18, 19]
[18, 19]
Corollary 2
Corollary 2

Table 3: Interprocedural same-context shortest path for RSMs with constant treewidth.
problem with the classical BFS/DFS algorithm [21], or with fast matrix multiplication [22]). In no preprocessing,
there is no preprocessing done, and the algorithm for one single-source query is used on demand for each individual query. We consider various other possible tradeoffs in preprocessing vs query time. Our main contributions
are as follows:
1. (General result). Since we consider arbitrary semirings (i.e., not restricted to finite semirings) we consider
the stack height bounded problem, where the height of the stack is bounded by a parameter h. While in
general for arbitrary semirings there does not exist a bound on the stack height, if the semiring contains
subsets of a finite universe D, and the semiring plus operator is intersection or union, then solving the
problem with sufficiently large bound on the stack height is equivalent to solving the problem without any
restriction on stack height. Our main result is an algorithm where the one-time preprocessing phase requires
O(n · log n + h · b · log n) semiring operations, and then each subsequent bounded stack height pair query
can be answered in constant number of semiring operations, where n is the number of nodes of the RSM
and b the number of boxes (see Table 1 and Theorem 3). If we specialize our result to the IFDS/IDE setting
with finite semirings from a finite universe of distributive functions 2D → 2D , and meet over all paths as
the semiring plus operator, then we obtain the results shown in Table 2 (Corollary 1). For example, our
approach with a factor of O(log n) overhead for one-time preprocessing, as compared no preprocessing,
can answer subsequent pair queries by a factor of O(n · |D|) faster. An important feature of our algorithms
is that they are simple and implementable.
2. (Reachability and shortest path). We now discuss the significance of our result for the very important special
cases of reachability and shortest path.
• (Reachability). The result for reachability with full preprocessing, no preprocessing, and the various
tradeoff that can be obtained by our approach is obtained from Table 2 by |D| = 1. For example
for pair queries, full preprocessing requires quadratic time and space (for all-pairs reachability computation) and answers individual queries in constant time; no preprocessing requires linear time and
space for individual queries; whereas with our approach (i) with almost-linear (O(n · log n)) preprocessing time and space we can answer individual queries in constant time, which is a significant (from
quadratic to almost-linear) improvement over full preprocessing; or (ii) with linear space and almostlinear preprocessing time we can answer queries in logarithmic time, which is a huge (from linear to
logarithmic) improvement over no preprocessing. For example, if we consider O(n) pair queries, then
both full preprocessing and no preprocessing in total require quadratic time, whereas our approach in
total requires O(n · log n + n · log n) = O(n · log n) time.
• (Shortest path). We now consider the problem of shortest path, where the current best-known algorithm is for pushdown graphs [18, 19] and we are not aware of any better bounds for RSMs (that have
unique entries and exits). The algorithm of [18] is a polynomial-time algorithm of degree four, and
the full preprocessing requires O(n5 ) time and quadratic space, and can answer single-source (resp.
pair) queries in linear (resp. constant time); whereas the no preprocessing requires O(n4 ) time and
linear space for both single-source and pair queries. In contrast, we show that (i) with almost-quadratic

3

(O(n2 · log n)) preprocessing time and almost-linear space, we can answer single-source (resp. pair)
queries in linear (resp. constant) time; or (i) with almost-quadratic preprocessing and linear space, we
can answer single-source (resp. pair) queries in linear (resp. logarithmic) time. Thus our approach
provides a significant theoretical improvement over the existing approaches.
There are two facts that are responsible for our improvement, the first is that we consider that each CSM
of the RSM has constant treewidth, and the second is the tradeoff of one-time preprocessing and individual
queries. Also note that our results apply only to same-context queries.
3. (Experimental results). Besides the theoretical improvements, we demonstrate the effectiveness of our approach on several well-known benchmarks from programming languages. We use the tool for computing
tree decompositions from [23], and all benchmarks of our experimental results have small treewidth. We
have implemented our algorithms for reachability (both intraprocedural and interprocedural) and shortest
paths (only intraprocedural), and compare their performance against complete and no preprocessing approaches for same-context queries. Our experimental results show that our approach obtains a significant
improvement over the existing approaches (of complete and no preprocessing).
Technical contribution. Our main technical contribution is a dynamic algorithm (also referred to as incremental
algorithm in graph algorithm literature) that given a graph with constant treewidth, after a preprocessing phase of
O(n · log n) semiring operations supports (1) changing the label of an edge with O(log n) semiring operations;
and (2) answering pair queries with O(log n) semiring operations; and (3) answering single-source queries with
O(n) semiring operations. These results are presented in Theorem 2.
Nice byproduct. Several previous works such as [24] have stated the importance and asked for the development of
data structures and analysis techniques to support dynamic updates. Though our main results are for the problem
where the RSM is given and fixed, our main technical contribution is a dynamic algorithm that can also be used
in other applications to support dynamic updates, and is thus also of independent interest.

1.1 Related Work
In this section we compare our work with several related work from interprocedural analysis as well as for constant
treewidth property.
Interprocedural analysis. Interprocedural analysis is a classic algorithmic problem in static analysis and several
diverse applications have been studied in the literature [1, 2, 3, 4, 5, 6, 7, 8, 9]. Our work is most closely related
to the IFDS/IDE frameworks introduced in seminal works [1, 2]. In both IFDS/IDE framework the semiring is
finite, and they study the algorithmic question of solving one single-source query. While in our framework the
semiring is not necessarily finite, we consider the stack height bounded problem. We also consider the multiple
pair and single-source, same-context queries, and the additional restriction that RSMs have constant treewidth.
Our general result specialized to finite semirings (where the stack height bounded problem coincides with the
general problem) improves the existing best known algorithms for the IFDS/IDE framework where the RSMs have
constant treewidth. For example, the shortest path problem cannot be expressed in the IFDS/IDE framework [18],
but can be expressed in the GPR framework [18, 19]. The GPR framework considers the more general problem of
weighted pushdown graphs, whereas we show that with the restriction to constant treewidth RSMs the bounds for
the best-known algorithm can be significantly improved. Finally, several works such as [24] ask for on-demand
interprocedural analysis and algorithms to support dynamic updates, and our main technical contributions are
algorithms to support dynamic updates in interprocedural analysis.
Recursive state machines (RSMs). Recursive state machines, which in general are equivalent to pushdown graphs,
have been studied as a formal model for interprocedural analysis [13]. However, in comparison to pushdown
graphs, RSMs are a more convenient formalism for interprocedural analysis. Games on recursive state machines
with modular strategies have been considered in [25, 26], and subcubic algorithm for general RSMs with reachability has been shown in [27]. We focus on RSMs with unique entries and exits and with the restriction that
the components have constant tree width. RSMs with unique entries and exits are less expressive than pushdown
graphs, but remain a very natural model for efficient interprocedural analysis [1, 2].
Treewidth of graphs. The notion of treewidth for graphs as an elegant mathematical tool to analyze graphs was
introduced in [14]. The significance of constant treewidth in graph theory is huge mainly because several problems

4

on graphs become complexity-wise easier. Given a tree decomposition of a graph with low treewidth t, many NPcomplete problems for arbitrary graphs can be solved in time polynomial in the size of the graph, but exponential
in t [28, 29, 30, 31, 32]. Even for problems that can be solved in polynomial time, faster algorithms can be
obtained for low treewidth graphs, for example, for the distance problem [20]. The constant-treewidth property of
graphs has also been used in the context of logic: Monadic Second Order (MSO) logic is a very expressive logic,
and a celebrated result of [33] showed that for constant-treewidth graphs the decision questions for MSO can be
solved in polynomial time; and the result of [34] shows that this can even be achieved in deterministic log-space.
Dynamic algorithms for the special case of 2-treewidth graphs has been considered in [35] and extended to various
tradeoffs by [36]; and [37] shows how to maintain the strongly connected component decomposition under edge
deletions for constant treewidth graphs. However, none of these works consider RSMs or interprocedural analysis.
Various other models (such as probabilistic models of Markov decision processes and games played on graphs for
synthesis) with the constant-treewidth restriction have also been considered [38, 39]. The problem of computing
a balanced tree decomposition for a constant treewidth graph was considered in [40], and we use this algorithm in
our preprocessing phase. More importantly, in the context of programming languages, it was shown by [16] that
the control flow graph for goto-free programs for many programming languages have constant treewidth. This
theoretical result was subsequently followed up in several practical approaches, and it was shown in [17] that
though in theory Java programs might not have constant treewidth, in practice Java programs do have constant
treewidth. We also use the existing tree-decomposition tool developed by [23] in our experimental results.

2 Definitions
We will in this section give definitions related to semirings, graphs, and recursive state machines.

2.1 Semirings
Definition 1 (Semirings). We consider partially complete semirings (Σ, ⊕, ⊗, 0, 1) where Σ is a countable set, ⊕
and ⊗ are binary operators on Σ, and 0, 1 ∈ Σ, and the following properties hold:
1.
2.
3.
4.
5.
6.

⊕ is associative, commutative, and 0 is the neutral element,
⊗ is associative, and 1 is the neutral element,
⊗ distributes over ⊕,
⊕ is infinitely associative,
⊗ infinitely distributes over ⊕,
0 absorbs in multiplication, i.e., ∀a ∈ Σ : a ⊗ 0 = 0.

Additionally, we consider that semirings are equipped with a closure operator ∗ , such that ∀s ∈ Σ : s∗ =
1 ⊕ (s ⊗ s∗ ) = 1 ⊕ (s∗ ⊗ s).

2.2 Graphs and tree decomposition
Definition 2 (Graphs and weighted paths). Let G = (V, E) be a finite directed graph where V is a set of n nodes
and E ⊆ V × V is an edge relation of m edges, along with a weight function wt : E → Σ that assigns to each
edge of G an element from Σ. A path P : u
v is a sequence of edges (e1 , . . . , ek ) and each ei = (xi , yi ) is
such that x1 = u, yk = v, and for all 1 ≤ i ≤ k − 1 we have yi = xi+1 . The length of P is k − 1. A path P is
simple if no node repeats in the path (i.e., it does not containN
a cycle). A single node is by itself a 0-length path.
Given a path P = (e1 , . . . , ek ), the weight of P is ⊗(P ) = (wt(e
L1 ), . . . , wt(ek )) if |P | ≥ 1 else ⊗(P ) = 1.
Given nodes u, v ∈ V , the distance d(u, v) is defined as d(u, v) = P :u v ⊗(P ), and d(u, v) = 0 if no such P
exists.
Definition 3 (Tree decomposition and treewidth [14, 31]). Given a graph G = (V, E), a tree-decomposition
Tree(G) = (VT , ET ) is a tree such that the following conditions hold:
S
1. VT = {B0 , . . . , Bn′ −1 : for all 0 ≤ i ≤ n′ − 1, Bi ⊆ V } and Bi ∈VT Bi = V .
2. For all (u, v) ∈ E there exists Bi ∈ VT such that u, v ∈ Bi .
5

2, 8, 10
2

3

5

8

10

7

1

9

6

2, 3, 10

8 9 10
7, 8, 9

1, 8, 9
6, 7, 9

4, 6, 9

4

5, 6, 7

Figure 1: A graph G with treewidth 2 (left) and a corresponding tree-decomposition Tree(G) (right).
3. For all i, j, k such that there exist paths Bi

Bk and Bk

Bj in Tree(G), we have Bi ∩ Bj ⊆ Bk .

The sets Bi which are nodes in VT are called bags. The width of a tree-decomposition Tree(G) is the size of the
largest bag minus 1 and the treewidth of G is the width of a minimum-width tree decomposition of G. It follows
from the definition that if G has constant treewidth, then m = O(n).
Example 1 (Graph and tree decomposition). The treewidth of a graph G is an intuitive measure which represents
the proximity of G to a tree, though G itself not a tree. The treewidth of G is 1 precisely if G is itself a tree [14].
Consider an example graph and its tree decomposition shown in Figure 1. It is straightforward to verify that all
the three conditions of tree decomposition are met. Each node in the tree is a bag, and labeled by the set of nodes
it contains. Since each bag contains at most three nodes, the tree decomposition by definition has treewidth 2.
Intuitive meaning of tree decomposition. In words, the tree-decomposition Tree(G) is a tree where every node
(bag) is subset of nodes of G, such that: (1) every vertex in G belongs to some bag; (2) every edge in G also
belongs to some bag; and (3) for every node v of G, for every subpath in Tree(G), if v appears in the endpoints
of the path, then it must appear all along the path.
Separator property. Given a graph G and its tree decomposition Tree(G), note that for each bag B in Tree(G),
if we remove the set of nodes in the bag, then the graph splits into possibly multiple components (i.e., each bag is
a separator for the graph). In other words, every bag acts as a separator of the graph.
Notations for tree decomposition. Let G be a graph, T = Tree(G), and B0 be the root of T . Denote with
Lv (Bi ) the depth of Bi in T , with Lv (B0 ) = 0. For u ∈ V , we say that a bag B introduces u if B is the bag
with the smallest level among all bags that contain u, i.e., Bu = arg minB∈VT : u∈B Lv (B). By definition, there
is exactly one bag introducing each node u. We often write Bu for the bag that introduces the node u, and denote
with Lv(u) = Lv (Bu ). Finally, we denote with B(u,v) the bag of the highest level that introduces one of u, v. A
tree-decomposition Tree(G) is semi-nice if Tree(G) is a binary tree, and every bag introduces at most one node.
Example 2. In the example of Figure 1, the bag {2, 8, 10} is the root of Tree(G), the level of node 9 is Lv(9) =
Lv({8, 9, 10}) = 1, and the bag of the edge (9, 1) is B(9,1) = {1, 8, 9}.
Theorem 1. (1) For every graph there exists a semi-nice tree decomposition that achieves the treewidth of G and
uses n′ = O(n) bags [41]. (2) For constant treewidth graphs, a balanced tree decomposition can be obtained in
O(n · log n) time (i.e., every simple path B0
Bi in Tree(G) has length O(log n)) [40].
The algebraic path problem on graphs of constant treewidth. Given G = (V, E), a balanced, semi-nice treedecomposition Tree(G) of G with constant treewidth t = O(1), a partially complete semiring (Σ, ⊕, ⊗, 0, 1), a
weight function wt : E → Σ, the algebraic path problem on input u, v ∈ V , asks for the distance d(u, v) from
node u to node v. In addition, we allow the weight function to change between successive queries. We measure
the time complexity of our algorithms in number of operations, with each operation being either a basic machine
operation, or an application of one of the operators of the semiring.

6

2.3 Recursive state machines
Definition 4 (RSMs and CSMs). A single-entry single-exit recursive state machine (RSM from now on) over an
alphabet Σ, as defined in [13], consists of a set {A1 , A2 , . . . , Ak }, such that for each 1 ≤ i ≤ k, the component
state machine (CSM) Ai = (Bi , Yi , Vi , Ei , wti ), where Vi = Ni ∪ {Eni } ∪ {Exi } ∪ Ci ∪ Ri , consists of:
• A set Bi of boxes.
• A map Yi , mapping each box in Bi to an index in {1, 2, . . . , k}. We say that a box b ∈ Bi corresponds to
the CSM with index Yi (b).
• A set Vi of nodes, consisting of the union of the sets Ni , {Eni }, {Exi }, Ci and Ri . The number ni is the
size of Vi . Each of these sets, besides Vi , are w.l.o.g. assumed to be pairwise disjoint.
– The set Ni is the set of internal nodes.
– The node Eni is the entry node.
– The node Exi is the exit node.
– The set Ci is the set of call nodes. Each call node is a pair (x, b), where b is a box in Bi and x is the
entry node EnYi (b) of the corresponding CSM with index Yi (b).
– The set Ri is the set of return nodes. Each return node is a pair (y, b), where b is a box in Bi and y is
the exit node ExYi (b) of the corresponding CSM with index Yi (b).
• A set Ei of internal edges. Each edge is a pair in (Ni ∪ {Eni } ∪ Ri ) × (Ni ∪ {Exi } ∪ Ci ).
• A map wti , mapping each edge in Ei to a label in Σ.
Definition 5 (Control flow graph of CSMs and treewidth of RSMs). Given a RSM A = {A1 , A2 , . . . , Ak }, the
control flow graph Gi = (Vi , Ei′ ) for CSM Ai consists of Vi as the set of vertices and Ei′ as the set of edges, where
Ei′ consists of the edges Ei of Ai and for each box b, each call node (v, b) of that box (i.e. for v = EnYi (b) ) has an
edge to each return node (v ′ , b) of that box (i.e. for v ′ = ExYi (b) ). We say that the RSM has treewidth t, if t is the
smallest integer such that for each index 1 ≤ i ≤ k, the graph Gi = (Vi , Ei′ ) has treewidth at most t. Programs
are naturally represented as RSMs, where the control flow graph of each method of a program is represented as a
CSM.
Example 3 (RSM and tree decomposition). Figure 2 shows an example of a program for matrix multiplication
consisting of two methods (one for vector multiplication invoked by the one for matrix multiplication). The
corresponding control flow graphs, and their tree decompositions that achieve treewidth 2 are also shown in the
figure.
Box sequences. For a sequence L of boxes and a box b, we denote with L ◦ b the concatenation of L and b. Also,
∅ is the empty sequence of boxes.
Configurations and global edges. A configuration of a RSM is a pair (v, L), where v is a node in (Ni ∪ {Eni } ∪
Ri ) and L is a sequence of boxes. The stack height of a configuration (v, L) is the number of boxes in the
sequence L. The set of global edges E are edges between configurations. The map wt maps each edge in E to a
label in Σ. We have that there is an edge between configuration c1 = (v1 , L1 ), where v1 ∈ Vi , and configuration
c2 = (v2 , L2 ) with label σ = wt(c1 , c2 ) if and only if one of the following holds:
• Internal edge: We have that v2 is an internal node in Ni and each of the following (i) L1 = L2 ; and
(ii) (v1 , v2 ) ∈ Ei ; and (iii) σ = wti ((v1 , v2 )).
• Entry edge: We have that v2 is the entry node EnYi (b) , for some box b, and each of the following (i) L1 ◦b =
L2 ; and (ii) (v1 , (v2 , b)) ∈ Ei ; and (iii) σ = wti ((v1 , (v2 , b))).
• Return edge: We have that v2 = (v, b) is a return node, for some exit node v = Exi and some box b and
each of the following (i) L1 = L2 ◦ b; and (ii) (v1 , v) ∈ Ei ; and (iii) σ = wti ((v1 , v)).
Note that in a configuration (v, L), the node v cannot be Exi or in Ci . In essence, the corresponding configuration
is at the corresponding return node, instead of at the exit node, or corresponding entry node, instead of at the call
node, respectively.
Execution paths. An execution path is a sequence of configurations and labels P = hc1 , σ1 , c2 , σ2 . . . , σℓ−1 , cℓ i,
such that for each integer i where 1 ≤ i ≤ ℓ − 1, we have that (ci , ci+1 ) ∈ E and σi = wt(ci , ci+1 ). We
call ℓ the length of P . Also, we say that the stack height of a execution path is the maximum stack height of
a configuration in the execution path. For a pair of configurations c, c′ , the set c
c′ , is the set of execution
′
paths hc1 , σ1 , c2 , σ2 . . . , σℓ−1 , cℓ i, for any ℓ, where c = c1 and c = cℓ . For a set S of execution paths, the set

7

B(S, h) ⊆ S is the subset of execution paths, with stack height at most h. Given a partially complete
semiring
N
(Σ, ⊕, ⊗, 0, 1), the distance of a execution path P = hc1 , σ1 , c2 , σ2 . . . , σℓ−1 , cℓ i is ⊗(P ) = (σ1 , . . . , σℓ−1 )
′
(the
distance d(c, c′ ) is defined as d(c, c′ ) =
L empty product is 1). Given configurations c, c , the configuration
′
h, where c′ is h-reachable
P :c c′ ⊗(P ) (the empty sum is 0). Also, given configurations c, c and a stack heightL
′
′
from c, the bounded height configuration distance d(c, c , h) is defined as d(c, c , h) = P :B(c c′ ,h) ⊗(P ). Note
that the above definition of execution paths only allows for so called valid paths [1, 2], i.e., paths that fully respect
the calling contexts of an execution.
The algebraic path problem on RSMs of constant tree-width. Given (i) a RSM A = {A1 , A2 , . . . , Ak }; and
(ii) for each 1 ≤ i ≤ k a balanced, semi-nice tree-decomposition Tree(Ai ) := Tree((Vi , Ei′ )) with constant
treewidth at most t = O(1); and (iii) a partially complete semiring (Σ, ⊕, ⊗, 0, 1), the algebraic path problem
on input nodes u, v, asks for the distance d((u, ∅), (v, ∅)), i.e. the distance between the configurations with the
empty stack. Similarly, also given a height h, the bounded height algebraic path problem on input configurations
c, c′ , asks for the distance d((u, ∅), (v, ∅), h). When it is clear from the context, we will write d(u, v) to refer to
the algebraic path problem of nodes u and v on RSMs.
Remark 1. Note that the empty stack restriction implies that u and v are nodes of the same CSM. However, the
paths from u to v are, in general, interprocedural, and thus involve invocations and returns from other CSMs. This
formulation has been used before in terms of same-context [27] and same-level [1] realizable paths and has several
applications in program analysis, e.g. by capturing balanced parenthesis-like properties used in alias analysis [42].
internal

entry

exit

Method: dot vector

1
2
3
4
5
6

Input: x, y ∈ Rn
Output: The dot product x⊤ y
result ← 0
for i ← 1 to n do
z ← x[i] · y[i]
result ← result + z
end
return result

return

call
1

1

B1

2

1, 2

B2

3

5

4

6

B3

2, 3

2, 5

B5

B4

2, 3, 4

5, 6

B6

Method: dot matrix

1
2
3
4
5
6
7
8

Input: A ∈ Rn×k , B ∈ Rk×m
Output: The dot product A × B
C ← zero matrix of size n × m
for i ← 1 to n do
for j ← 1 to m do
Call dot vector(A[i, :], B[:, j])
C[i, j] ← the value returned by the call of
line 4
end
end
return C

6

1

1

B1

2

1, 2

B2

3

7

4

8

B3
B4

3, 4

B5

3, 4, 5

5

2, 3

2, 7

B7

2, 3, 6

7, 8

B6

B8

Figure 2: Example of a program consisting of two methods, their control flow graphs Gi = (Vi , Ei′ ) where nodes
correspond to line numbers, and the corresponding tree decompositions, each one achieving treewidth 2.

2.4 Problems
We note that a wide range of interprocedural problems can be formulated as bounded height algebraic path problems.
1. Reachability i.e., given nodes u, v in the same CSM, is there a path from u to v? The problem can be
formulated on the boolean semiring ({True, False}, ∨, ∧, False, True).
2. Shortest path i.e., given a weight function wt : E → R≥0 and nodes u, v in the same CSM, what is the
weight of the minimum-weight path from u to v? The problem can be formulated on the tropical semiring
(R≥0 ∪ {∞}, min, +, ∞, 0).
8

3. Most probable path i.e., given a probability function P : E → [0, 1] and nodes u, v in the same CSM, what
is the probability of the highest-probable path from u to v? The problem can be formulated on the Viterbi
semiring ([0, 1], max, ·, 0, 1).
4. The class of interprocedural, finite, distributive, subset (IFDS) problems defined in [1]. Given a finite
domain D, a universe of flow functions F containing distributive functions f : 2D → 2D , a weight function
wt : E → F associates each edge with a flow function. The weight of an interprocedural path is then
defined as the composition ◦ of the flow functions along its edges, and the IFDS problem given nodes u, v
asks for the meet ⊓ (union or intersection) of the weights of all u
v paths. The problem can be formulated
on the meet-composition semiring (F, ⊓, ◦, ∅, I), where I is the identity function.
5. The class of interprocedural distributive environment (IDE) problems defined in [2]. This class of dataflow
problems is an extension to IFDS, with the difference that the flow functions (called environment transformers) map elements from the finite domain D to values in an infinite set (e.g., of the form f : D → N). An
environment transformer is denoted as f [d → ℓ], meaning that the element d ∈ D is mapped to value ℓ,
while the mapping of all other elements remains unchanged. The problem can be formulated on the meetenvironment-transformer semiring (F, ⊓, ◦, ∅, I), where I is the identity environment transformer, leaving
every map unchanged.
Note that if we assume that the set of weights of all interprocedural paths in the system is finite, then the size of
this set bounds the stack height h. Additionally, several problems can be formulated as algebraic path problems
in which bounding the stack height can be viewed as an approximation to them (e.g., shortest path with negative
interprocedural cycles, or probability of reaching a node v from a node u).

3 Dynamic Algorithms for Preprocess, Update and Query
In the current section we present algorithms that take as input a constant treewidth graph G and a balanced,
semi-nice tree-decomposition Tree(G) (recall Theorem 1), and achieve the following tasks:
1. Preprocessing the tree-decomposition Tree(G) of a graph G to answer algebraic path queries fast.
2. Updating the preprocessed Tree(G) upon change of the weight wt(u, v) of an edge (u, v).
3. Querying the preprocessed Tree(G) to retrieve the distance d(u, v) of any pair of nodes u, v.
In the following section we use the results of this section in order to preprocess RSMs fast, with the purpose
of answering interprocedural same-context algebraic path queries fast. Refer to Example 4 of Section 4 for an
illustration on how these algorithms are executed on an RSM.
First we establish the following lemma which captures the main intuition behind tree decompositions, namely,
that bags B of the tree-decomposition Tree(G) are separators between nodes of G that belong to disconnected
components of Tree(G) once B is removed.
Lemma 1 (Separator property). Consider a graph G = (V, E) and a tree-decomposition Tree(G). Let u, v ∈ V ,
and P ′ : B1 , B2 , . . . , Bj be the unique path in T such that u ∈ B1 and v ∈ Bj . For each i ∈ {1, . . . , j − 1} and
for each path P : u
v, there exists a node xi ∈ (Bi ∩ Bi+1 ∩ P ).
Proof. Fix a number i ∈ {1, . . . , j − 1}. We argue that for each path P : u
v, there exists a node xi ∈
(Bi ∩ Bi+1 ∩ P ). We construct a tree Tree′ (G), which is similar to Tree(G) except that instead of having an edge
between bag Bi and bag Bi+1 , there is a new bag B, that contains the nodes in Bi ∩ Bi+1 , and there is an edge
between Bi and B and one between B and Bi+1 . It is easy to see that Tree′ (G) forms a tree decomposition of
G. Let C1 , C2 be the two components of Tree(G) separated S
be B, and w.l.o.g.
S u ∈ C1 and v ∈ C2 . It follows by
the definition of tree decomposition that B is a separator of B ′ ∈C1 B ′ and B ′ ∈C2 B ′ . Hence, each path u
v
must go through some node xi in B, and by construction xi ∈ Bi ∩ Bi+1 .
Intuition and U-shaped paths. A central concept in our algorithms is that of U-shaped paths. Given a bag B and
nodes u, v ∈ B we say that a path P : u
v is U-shaped in B, if one of the following conditions hold:
1. Either |P | > 1 and for all intermediate nodes w ∈ P , we have Lv(w) ≥ Lv(B),
2. or |P | ≤ 1 and B is Bu or Bv .
Informally, given a bag B, a U-shaped path in B is a path that traverses intermediate nodes that are introduced
in B and its descendants in Tree(G). In the following we present three algorithms for (i) preprocessing a tree
9

decomposition, (ii) updating the data structures of the preprocessing upon a weight change wt(u, v) of an edge
(u, v), and (iii) querying for the distance d(u, v) for any pair of nodes u, v. The intuition behind the overall
approach is that for every path P : u
v and z = argminx∈P Lv(x), the path P can be decomposed to paths
P1 : u
z and P2 : z
v. By Lemma 1, if we consider the path P ′ : Bu
Bz and any bag Bi ∈ P ′ ,
we can find nodes x, y ∈ Bi ∩ P1 (not necessarily distinct). Then P1 is decomposed to a sequence of U-shaped
paths P1i , one N
for each such Bi , and the weight of P1 can be written as the ⊗-product of the weights of P1i ,
i.e., ⊗(P1 ) = (⊗(P1i )). Similar observation holds for P2 . Hence, the task of preprocessing and updating is to
summarize in each Bi the weights of all such U-shaped paths between all pairs of nodes appearing in Bi . To answer
the query, the algorithm traverses upwards the tree Tree(G) from Bu and Bv , and combines the summarized paths
to obtain the weights of all such paths P1 and P2 , and eventually P , such that ⊗(P ) = d(u, v).
Informal description of preprocessing. Algorithm Preprocess associates with each bag B a local distance map
LDB : B × B → Σ. Upon a weight change, algorithm Update updates the local L
distance map of some bags.
It will hold that after the preprocessing and each subsequent update, LDB (u, v) = P :u v {⊗(P )}, where all
P are U-shaped paths in B. Given this guarantee, we later present an algorithm for answering (u, v) queries
with d(u, v), the distance from u to v. Algorithm Preprocess is a dynamic programming algorithm. It traverses
Tree(G) bottom-up, and for a currently examined bag B introducing a node x, it calls the method Merge to
compute the local distance map LDB . In turn, Merge computes LDB depending only on the local distance maps
LDBi of the children {Bi } of B, and uses the closure operator ∗ to capture possibly unbdounded traversals of
cycles whose smallest-level node is x. See Method 1 and Algorithm 2 for a formal description.
Method 1: Merge

1
2
3
4
5
6
7
8
9

Input: A bag Bx with children {Bi }
Output: A local distance map LDBx
∗
N
Assign wt′ (x, x) ←
{LDB1 (x, x)∗ , . . . , LDBj (x, x)∗ }
foreach u ∈ Bx with u 6=Lx do
Assign wt′ (x, u) ← L{wt(x, u), LDB1 (x, u), . . . , LDBj (x, u)}
Assign wt′ (u, x) ← {wt(u, x), LDB1 (u, x), . . . , LDBj (u, x)}
end
foreach u, v ∈ BN
x do
Assign δ ← (wt′ (u, L
x), wt′ (x, x), wt′ (x, v))
Assign LDBx (u, v) ← {δ, LDB1 (u, v), . . . , LDBj (u, v)}
end

Algorithm 2: Preprocess
Input: A tree-decomposition Tree(G) = (VT , ET )
Output: A local distance map LDB for each bag B ∈ VT
1
2
3
4
5
6
7
8

Traverse Tree(G) bottom up and examine each bag B with children {Bi }
if B introduces some node x then
Assign LDB ← Merge on B
else
foreach u, v ∈ B do
L
Assign LDB (u, v) ← {LDB1 (u, v), . . . , LDBj (u, v)}
end
end

L
Lemma 2. At the end of Preprocess, for every bag B and nodes u, v ∈ B, we have LDB (u, v) = P :u v {⊗(P )},
where all P are U-shaped paths in B.
Proof. The proof is by induction on the parents. Initially, B is a leaf introducing some node x, thus each such path
P can only go through x, and hence will be captured by Preprocess. Now assume that the algorithm examines
a bag B, and by the induction hypothesis the statement is true for all {Bi } children of Bx . The correctness
follows easily if B does not introduce any node, since every such P is a U-shaped path in some child Bi of B.
Now consider that B introduces some node x, and any U-shaped path P ′ : u
v that additionally visits x, and
decompose it to paths P1 : u
x, P2 : x
x and P3 : x
v, such that x is not an intermediate node in either
10

P1 or P3 , and we have by distributivity:
M
⊗(P ′ ) =
P′

=

M O

(⊗(P1 ), ⊗(P2 ), ⊗(P3 ))

P1 ,P2 ,P3

O M

⊗(P1 ),

P1

M

⊗(P2 ),

P2

M

!

⊗(P3 )

P3

Note that P1 and P3 are also U-shaped in one of
, hence by the induction hypothesis
Lthe children bags Bi of BxL
in lines 3 and 2 of Merge we have wt′ (u, x) = P1 ⊗(P1 ) and wt′ (x, v) = P3 ⊗(P3 ). Also, by decomposing
P2 into a (possibly unbounded) sequence of paths P2i : x
x such that x is not intermediate node in any P2i , we
i
get that each such P2 is a U-shaped path in some child Bli of B, and we have by distributivity and the induction
hypothesis
M
M O
⊗(P21 ), ⊗(P22 ), . . .
⊗(P2 ) =
P21 ,P22 ,...

P2

=

M

Bl1 ,Bl2 ,...

=

M

Bl1 ,Bl2 ,...


O M

⊗(P21 ),

M

⊗(P22 ), . . .





O
LDBl1 (x, x), LDBl2 (x, x), . . .


P21

P22

and the
equals wt′ (x, x) from line 1 of Merge. The above conclude that in line 6 of Merge we have
L last expression
′
δ = P ′ ⊗(P ).

Finally, each U-shaped path P : u
v in B either visits x, or is U-shaped in one L
of the children Bi . Hence after
line 8 of Method Merge has run on B, for all u, v ∈ B we have that LDB (u, v) = P :u v ⊗(P ) where all paths
P are U-shaped in B. The desired results follows.

Lemma 3. Preprocess requires O(n) semiring operations.
Proof. Merge requires O(t2 ) = O(1) operations, and Preprocess calls Merge at most once for each bag, hence
requiring O(n) operations.
wt′ (x, x)
u

wt′ (u, x)

wt′ (x, v)

v

x
P1

P3
P2

Figure 3: Illustration of the inductive argument of Preprocess.
Informal description of updating. Algorithm Update is called whenever the weight wt(x, y) of an edge of G
has changed. Given the guarantee of Lemma 2, afterLUpdate has run on an edge update wt(x, y), it restores the
property that for each bag B we have LDB (u, v) = P :u v {⊗(P )}, where all P are U-shaped paths in B. See
Algorithm 3 for a formal description.
Lemma 4. At the end of each run of Update, for every bag B and nodes u, v ∈ B, we have LDB (u, v) =
L
P :u v {⊗(P )}, where all P are U-shaped paths in B.
Proof. First, by the definition of a U-shaped path P in B it follows that the statement holds for all bags not
processed by Update, since for any such bag B and U-shaped path P in B, the path P cannot traverse (u, v).
For the remaining bags, the proof follows an induction on the parents updated by Update, similar to that of
Lemma 2.
Lemma 5. Update requires O(log n) operations per update.
11

Algorithm 3: Update
Input: An edge (x, y) with new weight wt(x, y)
Output: A local distance map LDB for each bag B ∈ VT
1
2
3
4
5

Assign B ← B(x,y) , the highest bag containing the edge (x, y)
repeat
Call Merge on B
Assign B ← B ′ where B ′ is the parent of B
until Lv(B) = 0

Proof. Merge requires O(t2 ) = O(1) operations, and Update calls Merge once for each bag in the path from
B(u,v) to the root. Recall that the height of Tree(G) is O(log n) (Theorem 1), and the result follows.
Informal description of querying. Algorithm Query answers a (u, v) query with the distance d(u, v) from u
to v. Because of Lemma 1, every path P : u
v is guaranteed to go through the least common ancestor
(LCA) BL of Bu and Bv , and possibly some of the ancestors B of BL . Given this fact, algorithm Query uses
the procedure Climb to climb up the tree from Bu and Bv until it reaches
Tree(G). For
L BL and then the root of L
each encountered bag B along the way, it computes maps δu (w) = P1 {⊗(P1 )}, and δv (w) = P2 {⊗(P2 )}
where all P1 : u
w and P2 : w
v are such that each intermediate node y in them has been introduced
in B. This guarantees that for path P such that
N d(u, v) = ⊗(P ), when Query examines the bag Bz introducing
z = argminx∈P Lv(x), it will be d(u, v) =L (δN
u (z), δv (z)). Hence, for Query it suffices to maintain a current
best solution δ, and update it with δ ←
{δ, (δu (x), δv (x))} every time it examines a bag B introducing
some node x. Figure 4 presents a pictorial illustration of Query and its correctness. Method 4 presents the Climb
procedure which, given a current distance map of a node δ, a current bag B and a flag Up, updates δ with the
distance to (if Up = True), or from (if Up = False) each node in B. See Method 4 and Algorithm 5 for a formal
description.
Method 4: Climb
Input: A bag B, a map δ, a flag Up
Output: A new map δ
1
2
3
4
5
6
7
8
9

Remove from δ all w 6∈ B
Assign δ(w) ← 0 for all w ∈ B and not in δ
if B introduces node x then
if Up then
L
N
Update δ with δ(w) ← {δ(w), (δ(x), LDB (x, w))}
else
L
N
Update δ with δ(w) ← {δ(w), (δ(x), LDB (w, x))}
end
return δ

/* Climbing up */
/* Climbing down */

Lemma 6. Query returns δ = d(u, v).
Proof. Let P : u
v be any path from u to v, and z = argminx∈P
N Lv(x) the lowest level node in P . Decompose
P to P1 : u
z, P2 : z
v,L
and it follows that
⊗(P
)
=
(⊗(P1 ), ⊗(P2 )). We argue that when Query
L
examines Bz , it will be δu (z) = P1 ⊗(P1 ) and P2 δv (z) = ⊗(P2 ). We only focus on the δu (z) case here,
as the δv (z) is similar.
We argue inductively that when algorithm Query examines a bag Bx , for all w ∈ Bx we
L
have δu (w) = P ′ {⊗(P ′ )}, where all P ′ are such that for each intermediate node y we have Lv(y)
L ≥ Lv(x).
′
′
(x,
w)
=
Initially (line 1),
it
is
x
=
u,
B
=
B
,
and
every
such
P
is
U-shaped
in
B
,
hence
LD
x
u
u
B
x
P ′ {⊗(P )}
L
′
and δu (w) = P ′ {⊗(P )}. Now consider that Query examines a bag Bx (Lines 7 and 18) and the claim holds
for Bx′ a descendant of Bx previously examined by Query. If x does not occur in P ′ , it is a consequence of
Lemma 1 that w ∈ Bx′ , hence by the induction hypothesis, P ′ has been considered by Query. Otherwise, x
occurs inN
P ′ and decompose P ′ to P1′ , P2′ , such that P1′ ends with the first occurrenceLof x in P ′ , and it is
⊗(P ) = (⊗(P1′ ), ⊗(P2′ )). Note that P2′ is a U-shaped path in Bx , hence LDBx (x, w) = P ′ {⊗(P2′ )}. Finally,
2
L
as a consequence of Lemma 1, we have that x ∈ Bx′ , and by the induction hypothesis, δu (x) = P ′ {⊗(P1′ )}.
1
L
′
It follows that after Query processes Bx , it will be δu (w) =
P ′ {⊗(P )}. By the choice of z, when Query
12

Algorithm 5: Query
Input: A pair (u, v)
Output: The distance d(u, v) from u to v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Initialize map δu with δu (w) ← LDBu (u, w)
Initialize map δv with δv (w) ← LDBv (w, v)
Assign BL ← the LCA of Bu , Bv in Tree(G)
Assign B ← Bu
repeat
Assign B ← B ′ where B ′ is the parent of B
Call Climb on B and δu with flag Up set to True
until B = BL
Assign B ← Bv
repeat
Assign B ← B ′ where B ′ is the parent of B
Call Climb on B and δv with flag Up set to False
until B = BL
Assign B ←L
BL
Assign δ ← x∈BL ⊗(δu (x), δv (x))
repeat
Assign B ← B ′ where B ′ is the parent of B
Call Climb on B and δu with flag Up set to True
Call Climb on B and δv with flag Up set to False
if B introduces node
then
L xN
Assign δ ← {δ, (δu (x), δv (x))}
until Lv(B) = 0
return δ

L
examinesL
the bag Bz , it will be δu (z) = P1 {⊗(P
N 1 )}. A similar argument shows that at that point it will also be
δv (z) = P2 {⊗(P2 )}, hence at that point δ = (⊗(P1 ), ⊗(P2 )) = d(u, v).

Lemma 7. Query requires O(log n) semiring operations.
Proof. Climb requires O(t2 ) = O(1) operations and Query calls Climb once for every bag in the paths from Bu
and Bv to the root. Recall that the height of Tree(G) is O(log n) (Theorem 1), and the result follows.
Bz

Bx1 = BL

Bu

z

x1 z

u x1

Bx2

Bv

z x2

x2 v

Figure 4: Illustration of Query in computing the distance d(u, v) = ⊗(P ) as a sequence of U-shaped paths, whose
weight has been captured in the local distance map of each bag. When Bz is examined,N
with z = argminx∈P Lv(x),
it will be δu (z) = d(u, z) and δv (z) = d(z, v), and hence by distributivity d(u, v) = (δu (z), δv (z)).
We conclude the results of this section with the following theorem.

13

Theorem 2. Consider a graph G = (V, E) and a balanced, semi-nice tree-decomposition Tree(G) of constant
treewidth. The following assertions hold:
1. Preprocess requires O(n) semiring operations;
2. Update requires O(log n) semiring operations per edge weight update; and
3. Query correctly answers distance queries in O(log n) semiring operations.
Witness paths. Our algorithms so far have only been concerned with returning the distance d(u, v) of the pair
query u, v. When the semiring lacks the closure operator (i.e., for all s ∈ Σ it is s∗ = 1), as in most problems
e.g., reachability and shortest paths with positive weights, the distance from every u to v is realized by an acyclic
path. Then, it is straightforward to also obtain a witness path, i.e., a path P : u
v such that ⊗(P ) = d(u, v),
with some minor additional preprocessing. Here we outline how.
Whenever Merge updates the local distance LDB (u, v) between two nodes in a bag B, it does so by considering
the distances to and from an intermediate node x. It suffices to remember that intermediate node for every such
local distance. Then, the witness path to a local distance in B can be obtained straightforwardly by a top-down
computation on Tree(G) starting from B. Recall that in essence, Query answers a distance query u, v by combining several local distances along the paths Bu
Bz and Bz
Bv , where z is the node with the minimum level
in a path P : u
v such that ⊗(P ) = d(u, v). Since from every such local distance a witness sub-path Pi can be
obtained, P is reconstructed by juxtaposition of all such Pi . Finally, this process costs O(|P |) time.

4 Algorithms for Constant Treewidth RSMs
In this section we consider the bounded height algebraic path problem on RSMs of constant treewidth. That is,
we consider (i) an RSM A = {A1 , A2 , . . . , Ak }, where Ai consists of ni nodes and bi boxes; (ii) a partially
complete semiring (Σ, ⊕, ⊗, 0, 1); and (iii) a maximum stack height h. Our task is to create a datastructure
that after some preprocessing can answer queries of the form: Given a pair ((u, ∅), (v, ∅)) of configurations
compute d((u, ∅), (v, ∅), h) (also recall Remark 1). For this purpose, we present the algorithm RSMDistance,
which performs such preprocessing using a datastructure D consisting of the algorithms Preprocess, Update and
Query of Section 3. At the end of RSMDistance it will hold that algebraic path pair queries in a CSM Ai can be
answered in O(log ni ) semiring operations. We later present some additional preprocessing which suffers a factor
of O(log ni ) in the preprocessing space, but reduces the pair query time to constant.
Algorithm RSMDistance. Our algorithm RSMDistance can be viewed as a Bellman-Ford computation on the
call graph of the RSM (i.e., a graph where every node corresponds to a CSM, and an edge connects two CSMs if
one appears as a box in the other). Informally, RSMDistance consists of the following steps.
1. First, it preprocesses the control flow graphs Gi = (Vi , Ei′ ) of the CSMs Ai using Preprocess of Section 3,
where the weight function wti for each Gi is extended such that wti ((en, b), (ex, b)) = 0 for all pairs of call
and return nodes to the same box b. This allows the computation of d(u, v, 0) for all pairs of nodes (u, v),
since no call can be made while still having zero stack height.
2. Then, iteratively for each ℓ, where 0 ≤ ℓ ≤ h− 1, given that we have a dynamic datastructure D (concretely,
an instance of the dynamic algorithms Update and Query from Section 3) for computing d(u, v, ℓ), the
algorithm does as follows: First, for each Gi whose entry to exit distance d(Eni , Exi ) has changed from
the last iteration and for each Gj that contains a box pointing to Gi , it updates the call to return distance of
the corresponding nodes, using Query.
3. Then, it obtains the entry to exit distance d(Enj , Exj ) to see if it was modified, and continues with the next
iteration of ℓ + 1.
See Algorithm 6 for a formal description.
Correctness and logarithmic pair query time. The algorithm RSMDistance is described so that a proof by
induction is straightforward for correctness. Initially, running the algorithm Preprocess from Section 3 on each
of the graphs Gi allows queries for the distances d(u, v, 0) for all pairs of nodes (u, v), since no method call can
be made. Also, the induction follows directly since for every CSM Ai , updating the distance from call nodes
(en, b) to the corresponding return nodes (ex, b) of every box b that corresponds to a CSM Aj whose distance
d(Enj , Exj ) was changed in the last iteration ℓ, ensures that the distance d(u, v, ℓ + 1) of every pair of nodes
14

Algorithm 6: RSMDistance
Input: A set of control flow graphs G = {Gi }1≤i≤k , stack height h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

foreach Gi ∈ G do
Construct the tree-decomposition Tree(Gi )
Call Preprocess on Tree(Gi )
end
distances ← [Call Query on (Eni , Exi ) of Gi ]1≤i≤k
modified ← {1, . . . , k}
for ℓ ← 0 to h − 1 do
modified′ ← ∅
foreach i ∈ modified do
foreach Gj that contains boxes bj1 , . . . , bjl s.t. Yj (bjx ) = i do
Call Update on Gj for the weight change wt((en, bjl ), (ex, bjx )) ← distances[i]
Call Query on (Enj , Exj )
if d(Enj , Exj ) 6= distances[j] then
modified′ ← modified′ ∪ {j}
distances[j] ← d(Enj , Exj )
end
end
modified ← modified′
end

u, v in Ai is computed correctly. This is also true for the special pair of nodes Eni , Exi , which feeds the next
Pk
iteration of RSMDistance. Finally, RSMDistance requires O( i=1 (ni · log ni )) time to construct a balanced tree
Pk
decomposition (Theorem 1), O(n) time to preprocess all Gi initially, and O( i=1 (bi ·log ni )) to update all Gi for
Pk
one iteration of the loop of Line 4 (from Theorem 2). Hence, RSMDistance uses O( i=1 (ni ·log ni +h·bi ·log ni ))
preprocessing semiring operations. Finally, it is easy to verify that all preprocessing is done in O(n) space.
After the last iteration of algorithm RSMDistance, we have a datastructure D that occupies O(n) space and
answers distance queries d(u, v, h) in O(log ni ) time, with u, v ∈ Vi , by calling Query from Theorem 3 for the
distance d(u, v) in Gi .
Example 4. We now present a small example of how RSMDistance is executed on the RSM of Figure 2 for the
case of reachability. In this case, for any pair of nodes (u, v), we have d(u, v) = True iff u reaches v. Table 4(a)
illustrates how the local distance maps LDBx look for each bag Bx of each of the CSMs of the two methods
dot vector and dot matrix. Each column represents the local distance map of the corresponding bag Bx , and
an entry (u, v) means that LDBx (u, v) = True (i.e., u reaches v). For brevity, in the table we hide self loops
(i.e., entries of the form (u, u)) although they are stored by the algorithms. Initially, the stack height ℓ = 0, and
Preprocess is called for each graph (line 3). The new reachability relations discovered by Merge are shown in
bold. Note that at this point we have wt(4, 5) = False in method dot matrix, as we do not know whether the
call to method dot vector actually returns. Afterwards, Query is called to discover the distance d(1, 6) in method
dot vector (line 5). Table 4(b) shows the sequence in which Query examines the bags of the tree decomposition,
and the distances δ1 , δ6 and δ it maintains. When B2 is examined, δ = True and hence at the end Query returns
δ = True. Finally, since Query returns δ = True, the weight wt(4, 5) between the call-return pair of nodes (4, 5)
in method dot matrix is set to True. An execution of Update (line 11) with this update on the corresponding tree
decomposition (Table 4(a) for ℓ = 1) updates the entries (4, 5) and (4, 3) in LDB5 of method dot matrix (shown
in bold). From this point, any same-context distance query can be answered in logarithmic time in the size of its
CSM by further calls to Query.
Linear single-source query time. In order to handle single-source queries, some additional preprocessing is
required. The basic idea is to use RSMDistance to process the graphs Gi , and then use additional preprocessing
on each Gi by applying existing algorithms for graphs with constant treewidth. For graphs with constant treewidth,
an extension of Lemma 7 from [20] allows us to precompute the distance d(u, v) for every pair of nodes u, v ∈ Vi
that appear in the same bag of Tree(Gi ). The computation required is similar to Preprocess, with the difference
that this time Tree(Gi ) is traversed top-down instead of bottom-up. Additionally, for each examined bag B, a
Floyd-Warshall algorithm is run in the graph Gi induced by B, and all pairs of distances are updated. It follows

15

dot vector
ℓ/LDBx
ℓ=0

B1
−

B2
(1, 2)

B3
(2, 3)

−

(1, 2)

(2, 3)

(Preprocess)
ℓ=1
(Update)

B4
(2, 3)
(3, 4)
(4, 2)
(2, 4)
(2, 3)
(3, 4)
(4, 2)
(2, 4)

dot matrix
B5
(2, 5)

B6
(5, 6)

B1
−

B2
(1, 2)

B3
(2, 3)

B4
(3, 4)

B5
(3, 4)
(5, 3)

(2, 5)

(5, 6)

−

(1, 2)

(2, 3)

(3, 4)

(3, 4)
(5, 3)
(4, 5)
(4, 3)

B6
(2, 6)
(3, 6)
(6, 2)
(3, 2)
(2, 6)
(3, 6)
(6, 2)
(3, 2)

B7
(2, 7)

B8
(7, 8)

(2, 7)

(7, 8)

(a)

dot vector
Query
d(1, 6)

B6
δ6 = {5, 6}
−
−

B5
δ6 = {2, 5}
−
−

B2
δ6 = {1, 2}
δ1 = {1, 2}
δ = True

B1
δ6 = {1}
δ1 = {1}
δ = True

(b)

Table 4: Illustration of RSMDistance on the tree decompositions of methods dot vector and dot matrix from
Figure 2. Table (a) shows the local distance maps for each bag and stack height ℓ = 0, 1. Table (b) shows how
the distance query d(1, 6) in method dot vector is handled.
from Lemma 7 of [20] that for constant treewidth, this step requires O(ni ) time and space.
After all distances d(u, v) have been computed for each B, it is straightforward to answer single-source queries
from some node u in linear time. The algorithm simply maintains a map A : Vi → Σ, and initially A(v) = d(u, v)
for all v ∈ Bu , and A(v) = 0 otherwise. Then, it traverses Tree(G
) in a BFS manner starting at Bu , and for every
iN
L
encountered bag B and v ∈ B, if A(v) = 0, it sets A(v) = z∈B (A(z), d(z, v)). For constant treewidth, this
results in a constant number of semiring operations per bag, and hence O(ni ) time in total.
Constant pair query time. After RSMDistance has returned, it is possible to further preprocess the graphs
Gi to reduce the pair query time to constant, while increasing the space by a factor of log ni . For constant
treewidth, this can be obtained by adapting Theorem 10 from [20] to our setting, which in turn is based on a rather
complicated algorithmic technique of [43]. We present a more intuitive, simpler and implementable approach that
has a dynamic programming nature. In Section 5 we present some experimental results obtained by this approach.
Recall that the extra preprocessing for answering single-source queries in linear time consists in computing d(u, v)
for every pair of nodes u, v that appear in the same bag, at no overhead. To handle pair queries in constant time, we
further traverse each Tree(Gi ) one last time, bottom-up, and for each node u we store maps Fu , Tu : ViBu → Σ,
where ViBu is the subset of Vi of nodes that appear in Bu and its descendants in Tree(Gi ). The maps are such
that Fu (v) = d(u, v) and Tu = d(v, u). Hence, Fu stores the distances from u to nodes in ViBu , and Tu stores the
distances from nodes in ViBu to u. The maps are computed in a dynamic programming fashion, as follows:
1. Initially, the maps Fu and Tu are constructed for all u that appear in a bag B which is a leaf of Tree(Gi ). The
information required has already been computed as part of the preprocessing for answering single-source
queries. Then, Tree(Gi ) is traversed up, level by level.
2. When examining a bag B such that the computation
been performed for all its children, for evL has N
B
ery
node
u
∈
B
and
v
∈
V
,
we
set
F
(v)
=
{d(u, z), Fz (v)}, and similarly for Tu =
u
i
z∈B
L
N
{d(z,
u),
T
(v)}.
z
z∈B

An application of Lemma 1 inductively on the levels processed by the algorithm can
L be used to show that when
aLbag B is processed, for every node u ∈ B and v ∈ ViB , we have Tu (v) =
P :v u ⊗(P ) and Fu (v) =
P :u v ⊗(P ). Finally, there are O(ni ) semiring operations done at each level of Tree(Gi ), and since there are
O(log ni ) levels, O(ni · log ni ) operations are required in total. Hence, the space used is also O(ni · log ni ). We
furthermore preprocess Tree(Gi ) in linear time and space to answer LCA queries in constant time (note that since
Tree(Gi ) is balanced, this is standard). To answer aL
pair query
N u, v, it suffices to first obtain the LCA B of Bu
and Bv , and it follows from Lemma 1 that d(u, v) = z∈B {Tz (u), Fz (v)}, which requires a constant number
16

of semiring operations.
We conclude the results of this section with the following theorem. Afterwards, we obtain the results for the
special cases of the IFDS/IDE framework, reachability and shortest path.
Theorem 3. Fix the following input: (i) a constant treewidth RSM A = {A1 , A2 , . . . , Ak }, where Ai consists
of ni nodes and bi boxes; (ii) a partially complete semiring (Σ, ⊕, ⊗, 0, 1); and (iii) a maximum stack height h.
P
RSMDistance uses O( ki=1 (ni · log ni + h · bi · log ni )) preprocessing semiring operations and

1. Using O(n) space it correctly answers same-context algebraic pair queries in O(log ni ), and same-context
algebraic single-source queries in O(ni ) semiring operations.
Pk
2. Using O( i=1 (ni · log ni )) space, it correctly answers same-context algebraic pair queries in O(1) semiring operations.

IFDS/IDE framework. In the special case where the algebraic path problem belongs to the IFDS/IDE framework,
we have a meet-composition semiring (F, ⊓, ◦, ∅, I), where F is a set of distributive flow functions 2D → 2D ,
D is a set of data facts, ⊓ is the meet operator (either union or intersection), ◦ is the flow function composition
operator, and I is the identity flow function. For a fair comparison, the ◦ semiring operation does not induce a unit
time cost, but instead a cost of O(|D|) per data fact (as functions are represented as bipartite graphs [1]). Because
the set D is finite, and the meet operator is either union or intersection, it follows that the image of every data fact
will be updated at most |D| times. Then, line 7 of RSMDistance needs to change so that instead of h iterations,
the body of the loop is carried up to a fixpoint. The amortized cost per Gi is then bi · log ni · |D|3 (as there are |D|
data facts), and we have the following corollary (also see Table 2).
Corollary 1 (IFDS/IDE). Fix the following input a (i) constant treewidth RSM A = {A1 , A2 , . . . , Ak }, where
Ai consists of ni nodes and bi boxes; and (ii) a meet-composition semiring (F, ⊓, ◦, ∅, I) where F is a set of
distributive flow functions D → D, ◦ is the flow function composition operator and ⊓ is the meet operator.
Pk
1. Algorithm RSMDistance uses O( i=1 (ni · |D|2 + bi · log ni · |D|3 + ni · log ni )) preprocessing time,
O(n · |D|2 ) space, and correctly answers same-context algebraic pair queries in O(log ni · |D|2 ) time, and
same-context algebraic single-source queries in O(ni · |D|2 ) time.
P
2. Algorithm RSMDistance uses O( ki=1 (ni · log ni · |D|2 + bi · log ni · |D|3 )) preprocessing time, O(|D|2 ·
Pk
2
i=1 (ni · log ni )) space, and correctly answers same-context algebraic pair queries in O(|D| ) time, and
same-context algebraic single-source queries in O(ni · |D|2 ) time.
Reachability. The special case of reachability is obtained by setting |D| = 1 in Corollary 1.
Shortest paths. The shortest path problem can be formulated on the tropical semiring (R≥0 ∪{∞}, min, +, ∞, 0).
We consider that both semiring operators cost unit time (i.e., the weights occurring in the computation fit in a
constant number of machine words). Because we consider non-negative weights, it follows that the distance
between any pair of nodes is realized by a path that traverses every entry node at most once. Hence, we set h = k
in Theorem 3, and obtain the following corollary for shortest paths (also see Table 3).
Corollary 2 (Shortest paths). Fix the following input a (i) constant treewidth RSM A = {A1 , A2 , . . . , Ak }, where
Ai consists of ni nodes and bi boxes; (ii) a tropical semiring (R≥0 ∪ {∞}, min, +, ∞, 0). RSMDistance uses
Pk
O( i=1 (ni · log ni + k · bi · log ni )) preprocessing time and:
1. Using O(n) space, it correctly answers same-context shortest path pair queries in O(log ni ), and samecontext shortest path single-source queries in O(ni ) time.
P
2. Using O( ki=1 (ni · log ni )) space, it correctly answers same-context shortest path pair queries in O(1)
time.

Interprocedural witness paths. As in the case of simple graphs from Section 3, we can retrieve a witness path
for any distance d(u, v, h) that is realized by acyclic interprocedural paths P : (u, ∅)
(v, ∅), without affecting
the stated complexities. The process is straightforward. Let Ai contain the pair of nodes u, v on which the query
is asked. Initially, we obtain the witness intraprocedural path P ′ : u
v, as described in Section 3. Then, we
proceed recursively to obtain a witness path Pj between the entry Enj and exit Exj nodes of every CSM Aj
such that P ′ contains an edge between a call node (en, b) and a return node (ex, b) with Yi (B) = j. That is, we
reconstruct a witness path for every call to a CSM whose weight has been summarized locally in Ai . This process
constructs an interprocedural witness path P : u
v such that ⊗(P ) = d(u, v) in O(|P |) time.

17

5 Experimental Results
Benchmarks

Interprocedural Reachability
Preprocessing

antlr
bloat
chart
eclipse
fop
hsqldb
jython
luindex
lusearch
pmd
xalan
Jflex
muffin
javac
polyglot

n

t

Our

Complete

698
696
1159
656
1209
698
748
885
885
644
698
1091
1022
711
698

1.0
2.3
1.5
1.6
1.7
1.0
1.5
1.3
1.3
1.4
1.0
1.6
1.7
1.8
1.0

76316
27597
22191
37010
30189
55668
43609
36015
51375
31483
57734
51431
29905
32981
68643

136145
54335
90709
138905
91795
180333
68687
142005
189251
52527
138420
91742
66708
59793
150799

Intraprocedural Shortest path

Query
Single
Our
No Prepr.

Our

15.3
3.9
2.3
6.7
2.9
13.0
7.2
5.6
12.8
2.5
8.0
3.1
2.6
4.8
12.2

0.15
0.10
0.13
0.19
0.12
0.14
0.11
0.16
0.13
0.13
0.19
0.11
0.10
0.11
0.14

166.3
72.5
80.9
239.1
60.6
219.0
85.7
202.7
211.4
83.9
235.0
50.8
52.7
75.2
184.5

Preprocessing
Pair
No Prepr.
14.34
14.34
22.32
15.76
43.0
13.89
12.84
26.44
26.01
12.5
14.28
20.46
18.57
11.86
14.14

Our

Complete

Query
Single
Our
No Prepr.
Our

221578
87950
125468
152293
153728
215063
159085
163108
219015
140974
186695
154818
125938
117390
228758

1.13·107
1.15·107
1.24·108
1.07·107
3.94·108
1.23·107
1.42·107
2.97·107
2.90·107
9.14·106
1.10·107
1.24·108
1.02·108
1.31·107
1.15·107

251
257
398
533
1926
236
386
258
254
327
380
231
265
370
244

24576
25239
88856
23639
113689
24322
29958
51192
50719
22572
24141
83093
80878
26180
24400

0.36
0.37
0.39
0.46
2.71
0.36
0.32
0.37
0.34
0.37
0.43
0.36
0.38
0.34
0.35

Pair
No Prepr.
24576
25239
88856
23639
113689
24322
29958
51192
50719
22572
24141
83093
80878
26180
24400

Table 5: Average statistics gathered from our experiments on the DaCapo benchmark suit. Times are in microseconds.
Set up. We have implemented our algorithms for linear-time single-source and constant-time pair queries presented in Section 4 and have tested them on graphs obtained from the DaCapo benchmark suit [44] that contains
several, real-world Java applications. Every benchmark is represented as a RSM that consists of several CSMs,
and each CSM corresponds to the control flow graph of a method of the benchmark. We have used the Soot
framework [45] for obtaining the control flow graphs, where every node of the graph corresponds to one Jimple
statement of Soot, and the tool of [23] to obtain their tree decompositions. Our experiments were run on a standard
desktop computer with a 3.4GHz CPU, on a single thread.
Interprocedural reachability and intraprocedural shortest path. In our experiments, we focus on the important special case of reachability and shortest path. We consider CSMs of moderate to large size (all CSMs
with at least five hundred nodes), as for small CSMs the running times are negligible. The first step is to execute an interprocedural reachability algorithm from the program entry to discover all actual call to return edges
((en, b), (ex, b)) of every CSM Ai (i.e., all invocations that actually return), and then consider the control flow
graphs Gi independently.
• (Reachability). For every Gi , the complete preprocessing in the case of reachability is done by executing
ni DFSs, one from each source node. The single-source query from u is answered by executing one DFS
from u, and the pair query u, v is done similarly, but we stop as soon as v is reached. We note that this
methodology correctly answers interprocedural same-context reachability queries.
• (Shortest path). For shortest path we perform intraprocedural analysis on each Gi . We assign both positive
and negative weights to each edge of Gi uniformly at random from the range [−10, 10]. For general semiring path properties, the Bellman-Ford algorithm [21] is a very natural one, which in the case of shortest
path can handle positive and negative weights, as long as there is no negative cycle. To have a meaningful comparison with Bellman-Ford (as a representative of a general semiring framework), we consider
both positive and negative weights, but do not allow negative cycles. For complete preprocessing we run
the classical Floyd-Warshall algorithm (which computes all-pairs shortest paths and is a generalization of
Bellman-Ford). Under no preprocessing, for every single-source and pair query we run the Bellman-Ford
algorithm.
Results. Our experimental results are shown in Table 5.
1. The average treewidth of control flow graphs is confirmed to be very small, and does not scale with the size
of the graph. In fact, even the largest treewidth is four.
2. The preprocessing time of our algorithm is significantly less than the complete preprocessing, by factor
of 1.5 to 4 times in case of reachability, and by orders of magnitude in case of shortest path.

18

3. In both reachability and shortest path, all queries are handled significantly faster after our preprocessing,
than no preprocessing. We also note that for shortest path queries, Bellman-Ford answers single-source and
pair queries in the same time, which is significantly slower than both our single-source and pair queries. Finally, we note that for single-source reachability queries, though we do not provide theoretical improvement
over DFS (Table 2), the one-time preprocessing information allows for practical improvements.
Since our work focuses on same-context queries and the IFDS/IDE framework does not have this restriction, a
direct comparison with the IFDS/IDE framework would be biased in our favor. In the experimental results for
interprocedural reachability with same-context queries, we show that we are faster than even DFS (which is faster
than IFDS/IDE).
Description of Table 5. In the table, the second (resp. third) column shows the average number of nodes (resp.
treewidth) of CSMs of each benchmark. The running times of preprocessing are gathered by averaging over all
CSMs in each benchmark. The running times of querying are gathered by averaging over all possible single-source
and pair queries in each CSM, and then averaging over all CSMs in each benchmark.

6 Conclusions
In this work we considered constant treewidth RSMs since control flow graphs of most programs have constant
treewidth. We presented algorithms to handle multiple same-context algebraic path queries, where the weights
belong to a partially complete semiring. Our algorithms have small additional one-time preprocessing, but answer
subsequent queries significantly faster than no preprocessing both in terms of theoretical bounds as well as in
practice, even for basic problems such as reachability and shortest path. While in this work we focused on RSMs
with unique entries and exits, an interesting theoretical question is to extend our results to RSMs with multiple
entries and exists.
Acknowledgements. We thank anonymous reviewers for helpful comments to improve the presentation of the
paper.

References
[1] Thomas Reps, Susan Horwitz, and Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. In POPL, New York, NY, USA, 1995. ACM.
[2] Mooly Sagiv, Thomas Reps, and Susan Horwitz. Precise interprocedural dataflow analysis with applications
to constant propagation. Theor. Comput. Sci., 1996.
[3] David Callahan, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Interprocedural constant propagation.
In CC. ACM, 1986.
[4] Dan Grove and Linda Torczon. Interprocedural constant propagation: A study of jump function implementation. In PLDI. ACM, 1993.
[5] William Landi and Barbara G. Ryder. Pointer-induced aliasing: A problem classification. In POPL. ACM,
1991.
[6] Jens Knoop, Bernhard Steffen, and Jürgen Vollmer. Parallelism for free: Efficient and optimal bitvector
analyses for parallel programs. ACM Trans. Program. Lang. Syst., 1996.
[7] P. Cousot and R Cousot. Static determination of dynamic properties of recursive procedures. In E.J. Neuhold,
editor, IFIP Conf. on Formal Description of Programming Concepts, 1977.
[8] Robert Giegerich, Ulrich Möncke, and Reinhard Wilhelm. Invariance of approximate semantics with respect
to program transformations. In 3rd Conference of the European Co-operation in Informatics (ECI), 1981.
[9] Jens Knoop and Bernhard Steffen. The interprocedural coincidence theorem. In CC, 1992.

19

[10] Nomair A. Naeem and Ondrej Lhoták. Typestate-like analysis of multiple interacting objects. In OOPSLA,
2008.
[11] Xin Zhang, Ravi Mangal, Mayur Naik, and Hongseok Yang. Hybrid top-down and bottom-up interprocedural
analysis. In PLDI, 2014.
[12] Krishnendu Chatterjee, Andreas Pavlogiannis, and Yaron Velner. Quantitative interprocedural analysis. In
POPL, 2015.
[13] R. Alur, M. Benedikt, K. Etessami, P. Godefroid, T. W. Reps, and M. Yannakakis. Analysis of recursive state
machines. ACM Trans. Program. Lang. Syst., 2005.
[14] Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory,
Series B, 1984.
[15] Rudolf Halin. S-functions for graphs. Journal of Geometry, 1976.
[16] Mikkel Thorup. All Structured Programs Have Small Tree Width and Good Register Allocation. Information
and Computation, 1998.
[17] Jens Gustedt, OleA. Mæhle, and JanArne Telle. The treewidth of java programs. In Algorithm Engineering
and Experiments, LNCS. Springer, 2002.
[18] Thomas Reps, Stefan Schwoon, Somesh Jha, and David Melski. Weighted pushdown systems and their
application to interprocedural dataflow analysis. Sci. Comput. Program., 2005.
[19] Thomas Reps, Akash Lal, and Nick Kidd. Program analysis using weighted pushdown systems. In FSTTCS
2007: Foundations of Software Technology and Theoretical Computer Science, LNCS. 2007.
[20] Shiva Chaudhuri and Christos D. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica, 1995.
[21] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction To Algorithms. MIT Press, 2001.
[22] Michael J. Fischer and Albert R. Meyer. Boolean Matrix Multiplication and Transitive Closure. In SWAT
(FOCS). IEEE Computer Society, 1971.
[23] Thomas van Dijk, Jan-Pieter van den Heuvel, and Wouter Slob. Computing treewidth with libtw. Technical
report, University of Utrecht, 2006.
[24] Susan Horwitz, Thomas Reps, and Mooly Sagiv. Demand interprocedural dataflow analysis. SIGSOFT
Softw. Eng. Notes, 1995.
[25] R. Alur, S. La Torre, and P. Madhusudan. Modular strategies for recursive game graphs. Theor. Comput.
Sci., 2006.
[26] Krishnendu Chatterjee and Yaron Velner. Mean-payoff pushdown games. In LICS, 2012.
[27] Swarat Chaudhuri. Subcubic algorithms for recursive state machines. In POPL, New York, NY, USA, 2008.
ACM.
[28] Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial
k-trees . Discrete Appl Math, 1989.
[29] M.W Bern, E.L Lawler, and A.L Wong. Linear-time computation of optimal subgraphs of decomposable
graphs. J Algorithm, 1987.
[30] Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In ICALP, LNCS. Springer,
1988.
[31] Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 1993.
[32] HansL. Bodlaender. Discovering treewidth. In SOFSEM 2005: Theory and Practice of Computer Science,
volume 3381 of LNCS. Springer, 2005.
[33] Brouno Courcelle. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer
Science (Vol. B). MIT Press, Cambridge, MA, USA, 1990.

20

[34] M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of bodlaender and courcelle. In
FOCS, 2010.
[35] HansL. Bodlaender. Dynamic algorithms for graphs with treewidth 2. In Graph-Theoretic Concepts in
Computer Science, LNCS. Springer, 1994.
[36] Torben Hagerup. Dynamic algorithms for graphs of bounded treewidth. Algorithmica, 2000.
[37] J. Lacki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Transactions on Algorithms, 2013.
[38] K. Chatterjee and J. Lacki. Faster algorithms for Markov decision processes with low treewidth. In CAV,
2013.
[39] Jan Obdrzálek. Fast mu-calculus model checking when tree-width is bounded. In CAV, 2003.
[40] Bruce A. Reed. Finding approximate separators and computing tree width quickly. In STOC, 1992.
[41] Ton Kloks. Treewidth, Computations and Approximations. LNCS. Springer, 1994.
[42] Manu Sridharan, Denis Gopan, Lexin Shan, and Rastislav Bodı́k. Demand-driven points-to analysis for java.
In OOPSLA, 2005.
[43] Noga Alon and Baruch Schieber. Optimal preprocessing for answering on-line product queries. Technical
report, Tel Aviv University, 1987.
[44] Stephen M. et al. Blackburn. The dacapo benchmarks: Java benchmarking development and analysis. In
OOPSLA, 2006.
[45] Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot - a
java bytecode optimization framework. In CASCON ’99. IBM Press, 1999.

21

