Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains


Morten Kühnrich, Stefan Schwoon, Jiří Srba, and Stefan Kiefer. Interprocedural dataflow analysis over weight domains with infinite descending chains. Technical report,, 2009. Available at


We study generalized fixed-point equations over idempotent semirings and provide an efficient algorithm for the detection whether a sequence of Kleene's iterations stabilizes after a finite number of steps. Previously known approaches considered only bounded semirings where there are no infinite descending chains. The main novelty of our work is that we deal with semirings without the boundedness restriction. Our study is motivated by several applications from interprocedural dataflow analysis. We demonstrate how the reachability problem for weighted pushdown automata can be reduced to solving equations in the framework mentioned above and we describe a few applications to demonstrate its usability.

Suggested BibTeX entry:

    author = {Morten K\"uhnrich and Stefan Schwoon and Ji\v{r}\'{\i} Srba and Stefan Kiefer},
    institution = {},
    note = {Available at},
    title = {Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains},
    year = {2009}

PDF (242 kB)
See ...
Conference version