并发计算的元模型Ⅰ.图模型

Meta Model of Concurrent Computation Ⅰ.Graph Model

借鉴证明论中的一些思想 ,提出了并发计算的一个图模型 .在此模型中 ,计算对象表示为图 ,计算过程表示为图重写 ,重写规则将通信过程视为证明的等价变换过程 .为便于形式化研究图模型 ,提出了模型的形式对应物——图演算 ,该演算类似于进程代数演算 ,与其他进程代数演算的不同之处在于本演算是对称的 .文中用证明论方法研究并行理论 。

This is the first of a series of papers on concurrent computation models. A graph model was proposed for concurrent computation using ideas from proof theory. A computational object was represented by a graph while computation was modeled by graph rewriting under a communication as cut elimination paradigm. Formal account of the model was given in the framework of graph calculus. The significance of the model lies in that it initiates a proof theoretical approach to concurrency theory.