Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F09%3A00038049" target="_blank" >RIV/00216224:14330/09:00038049 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/09:00067163

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains

Popis výsledku v původním jazyce

We study generalized fixed-point equations over idempotent semirings and provide an efficient algorithm for the detection whether a sequence of Kleenes 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.

Název v anglickém jazyce

Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains

Popis výsledku anglicky

We study generalized fixed-point equations over idempotent semirings and provide an efficient algorithm for the detection whether a sequence of Kleenes 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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2009

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'09), pages 440-455, volume 5504 of LNCS, Springer-Verlag, 2009.

ISBN

978-3-642-00595-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

—

Název nakladatele

Springer Verlag

Místo vydání

Netherlands

Místo konání akce

Eindhoven

Datum konání akce

1. 1. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—