2007 | OriginalPaper | Buchkapitel
Program Analysis Using Weighted Pushdown Systems
verfasst von : Thomas Reps, Akash Lal, Nick Kidd
Erschienen in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Pushdown systems
(PDSs) are an automata-theoretic formalism for specifying a class of infinite-state transition systems. Infiniteness comes from the fact that each configuration
$\langle{p,S}\rangle$
in the state space consists of a (formal) “control location”
p
coupled with a stack
S
of unbounded size. PDSs can model program paths that have matching calls and returns, and automaton-based representations allow analysis algorithms to account for the infinite control state space of recursive programs.
Weighted pushdown systems
(WPDSs) are a generalization of PDSs that add a general “black-box” abstraction for program data (through
weights
). WPDSs also generalize other frameworks for interprocedural analysis, such as the Sharir-Pnueli functional approach.
This paper surveys recent work in this area, and establishes a few new connections with existing work.