Inductive Data Flow Graphs

به نام خدا

Title: Inductive Data Flow Graphs

Authors: Azadeh Farzan Zachary Kincaid, Andreas Podelski

Abstract: The correctness of a sequential program can be shown by the annotation of its control flow graph with inductive assertions. We pro-pose inductive data flow graphs, data flow graphs with incorporated inductive assertions, as the basis of an approach to verifying concurrent programs. An inductive data flow graph accounts for a set of dependencies between program actions in interleaved thread executions, and therefore stands as a representation for the set of concurrent program traces which give rise to these dependencies. The approach first constructs an inductive data flow graph and then checks whether all program traces are represented. The size of the inductive data flow graph is polynomial in the number of data dependencies (in a sense that can be made formal); it does not grow exponentially in the number of threads unless the data dependencies do. The approach shifts the burden of the exponential explosion towards the check whether all program traces are represented, i.e., to a combinatorial problem (over finite graphs).   

Publish Year: 2013

Published in: ACM-SIGPLAN-SIGACT

Number of Pages: 14

موضوع: نظریه گراف (Graph Theory)

مشاهده صفحه اول مقاله

دانلود مقاله

لینک مقاله در سایت ناشر

ایران سای – مرجع مقالات علمی فنی مهندسی

حامی دانش بومی ایرانیان