Efficient algorithms for pre* and post* on interprocedural parallel flow graphs
Efficient algorithms for pre* and post* on interprocedural parallel flow graphs
复制标题
过程间并行流图上 pre* 和 post* 的高效算法
DOI：
10.1145/325694.325697
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
A. Podelski
中科院分区：
文献类型：
--
作者：
J. Esparza;A. Podelski
本文是一个贡献已经存在的一系列工作的算法原则的过程间分析。我们考虑的情况下，并行程序的推广。我们给出了计算后向响应集的算法。并行流图系统在图的大小即程序的线性时间内的前向可达配置。这些操作在故障分析和模型检验中是很重要的。在我们的方法中，我们首先模型配置的进程代数PA，可以表达调用堆栈操作和并行性的条款（即树）。然后，我们给出了一个“声明性”霍恩子句规范的集合的前任分别。继任者这些集合的“运算”计算是使用HornSat的Dowling-Gallier程序进行的。
This paper is a contribution to the already existing series of work on the algorithmic principles of interprocedural analysis. We consider the generalization to the case of parallel programs. We give algorithms that compute the sets of backward resp. forward reachable configurations for parallel flow graph systems in linear time in the size of the graph viz. the program. These operations are important in dataflow analysis and in model checking. In our method, we first model configurations as terms (viz. trees) in the process algebra PA that can express call stack operations and parallelism. We then give a 'declarative' Horn-clause specification of the sets of predecessors resp. successors. The 'operational' computation of these sets is carried out using the Dowling-Gallier procedure for HornSat.