Download Now Free registration required
The authors 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 the work is that they deal with semirings without the boundedness restriction. The study is motivated by several applications from interprocedural dataflow analysis. They demonstrate how the reachability problem for weighted pushdown automata can be reduced to solving equations in the framework mentioned above and they describe a few applications to demonstrate its usability.
- Format: PDF
- Size: 242.51 KB