Inductive data flow graphs
- 23 January 2013
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 48 (1), 129-142
- https://doi.org/10.1145/2429069.2429086
Abstract
The correctness of a sequential program can be shown by the annotation of its control flow graph with inductive assertions. We propose 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).Keywords
This publication has 20 references indexed in Scilit:
- Refinement of Trace AbstractionLecture Notes in Computer Science, 2009
- Semantic Reduction of Thread Interleavings in Concurrent ProgramsLecture Notes in Computer Science, 2009
- Thread Quantification for Concurrent Shape AnalysisLecture Notes in Computer Science, 2008
- Trace Partitioning in Abstract Interpretation Based Static AnalyzersLecture Notes in Computer Science, 2005
- Abstract interpretation by dynamic partitioningJournal of Functional Programming, 1992
- The program dependence graph and its use in optimizationACM Transactions on Programming Languages and Systems, 1987
- AlternationJournal of the ACM, 1981
- On equations for regular languages, finite automata, and sequential networksTheoretical Computer Science, 1980
- Verifying properties of parallel programsCommunications of the ACM, 1976
- A new solution of Dijkstra's concurrent programming problemCommunications of the ACM, 1974