Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains

Morten Kühnrich, Stefan Schwoon, Jiri Srba, Stefan Kiefer

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind5504
Sider (fra-til)440-455
Antal sider15
ISSN0302-9743
DOI
StatusUdgivet - 2009
Begivenhed12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'09) - York, Storbritannien
Varighed: 22 mar. 200929 mar. 2009
Konferencens nummer: 12

Konference

Konference12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'09)
Nummer12
LandStorbritannien
ByYork
Periode22/03/200929/03/2009

Bibliografisk note

Titel:
12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'09)

Oversat titel:


Oversat undertitel:


Forlag:
Springer

ISBN (Trykt):
978-3-642-00595-4

ISBN (Elektronisk):


Publikationsserier:
Lecture Notes in Computer Science, Lecture Notes in Comptuer Science, 0302-9743, 1611-3349, 5504

Emneord

  • pushdown automata
  • program analysis
  • semiring

Citationsformater