Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Data Structure
dataflow analysis
Efficient Algorithm
Fixed Point Equation
Pushdown Automata
Related Publications
(1)
Weighted pushdown systems and their application to interprocedural dataflow analysis
Subscribe
Academic
Publications
Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains
Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains,10.1007/9783642005961_31,Computing Research Repository,Morte
Edit
Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Morten Kühnrich
,
Stefan Schwoon
,
Jiÿr ´ õ Srba
,
Stefan Kiefer
We study generalized fixedpoint 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 frame work mentioned above and we describe a few applications to demonstrate its usability.
Journal:
Computing Research Repository  CORR
, vol. abs/0901.0, pp. 440455, 2009
DOI:
10.1007/9783642005961_31
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www7.in.tum.de
)
(
www.model.in.tum.de
)
(
wwwbrauer.in.tum.de
)
(
www7.in.tum.de
)
(
www.model.informatik.tumuenchen.de
)
(
www.model.informatik.tumuenchen.de
)
(
wwwbrauer.in.tum.de
)
(
adsabs.harvard.edu
)
(
wwwbrauer.informatik.tumuenchen.de
)
(
www.model.in.tum.de
)
(
www7.in.tum.de
)
(
www7.informatik.tumuenchen.de
)
(
www.model.informatik.tumuenchen.de
)
(
wwwbrauer.in.tum.de
)
(
www.informatik.unitrier.de
)
(
www.informatik.unitrier.de
)
(
wwwbrauer.informatik.tumuenchen.de
)
(
www.brics.dk
)
(
www.model.in.tum.de
)
(
wwwbrauer.informatik.tumuenchen.de
)
(
dx.doi.org
)
(
arxiv.org
)
More »
Citation Context
(2)
...Additionally in recent work [12,
13
], new techniques have been presented to solve equations for more general types of semirings...
Alexander Wenner
.
Weighted Dynamic Pushdown Networks
...A full version of the paper is available as [
12
]...
...Our contribution is that we prove that it works also for polynomials of higher degrees where more involved technical treatment is necessary. Details are presented in [
12
]...
...treatment only for the predecessors; the computation of successors is analogous and it is provided in [
12
]...
...A similar conclusion about the complexity of the algorithm for computing successors can be drawn thanks to the (linear) connection between forward and backward reachability analysis described in [
12
]...
...The problem of computing successors is also considered in [20], i.e., computing a Wautomaton A where vA(c) is the meetoverallpaths from an initial configuration c0 to c. Using our technique, this result can also be extended to unbounded semirings; [
12
] shows an equation system for this problem, which can be converted into a Wautomaton for post ∗(c0) in analogous fashion...
...As mentioned in Section 3, this automaton can be normalized in linear time and we can then build a weighted post ∗({pX}) Wautomaton, of size O(n2) with O(n) states and in time O(n4). Details can be found in [
12
]...
Morten Kühnrich
,
et al.
Interprocedural Dataflow Analysis over Weight Domains with Infinite De...
References
(25)
Formal properties of XML grammars and languages
(
Citations: 25
)
Jean Berstel
,
Luc Boasson
Journal:
Acta Informatica  ACTA
, vol. 38, no. 9, pp. 649671, 2002
Rewriting Models of Boolean Programs
(
Citations: 12
)
Ahmed Bouajjani
,
Javier Esparza
Conference:
Rewriting Techniques and Applications  RTA
, pp. 136150, 2006
Efficient Algorithms for Model Checking Pushdown Systems
(
Citations: 188
)
Javier Esparza
,
David Hansel
,
Peter Rossmanith
,
Stefan Schwoon
Conference:
Computer Aided Verification  CAV
, pp. 232247, 2000
On Fixed Point Equations over Commutative Semirings
(
Citations: 16
)
Javier Esparza
,
Stefan Kiefer
,
Michael Luttenberger
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 296307, 2007
Abstraction Refinement with Craig Interpolation and Symbolic Pushdown Systems
(
Citations: 21
)
Javier Esparza
,
Stefan Kiefer
,
Stefan Schwoon
Conference:
Tools and Algorithms for Construction and Analysis of Systems  TACAS
, pp. 489503, 2006
Sort by:
Citations
(2)
Weighted Dynamic Pushdown Networks
Alexander Wenner
Conference:
European Symposium on Programming  ESOP
, pp. 590609, 2010
Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains
(
Citations: 2
)
Morten Kühnrich
,
Stefan Schwoon
,
Jiÿr ´ õ Srba
,
Stefan Kiefer
Journal:
Computing Research Repository  CORR
, vol. abs/0901.0, pp. 440455, 2009