论文标题
命令过程代数和计算模型
Imperative process algebra and models of computation
论文作者
论文摘要
与计算性和计算复杂性有关的问题的研究涉及使用计算模型。该模型的关键是考虑的计算过程。可以使用基于ACP（通信过程代数）的命令过程代数来描述此类过程。在本文中，研究了有关代数是否可以在计算模型领域中发挥作用。这证明了该过程代数适合以数学精确的计算模型来描述，该计算模型对应于基于顺序，异步平行的序列模型，以及同步的随机访问机器以及对这些模型和工作复杂度衡量的模型。还描述了基于顺序随机访问机和复杂性度量的模型的概率变体。
Studies of issues related to computability and computational complexity involve the use of a model of computation. Pivotal to such a model are the computational processes considered. Processes of this kind can be described using an imperative process algebra based on ACP (Algebra of Communicating Processes). In this paper, it is investigated whether the imperative process algebra concerned can play a role in the field of models of computation.It is demonstrated that the process algebra is suitable to describe in a mathematically precise way models of computation corresponding to existing models based on sequential, asynchronous parallel, and synchronous parallel random access machines as well as time and work complexity measures for those models. A probabilistic variant of the model based on sequential random access machines and complexity measures for it are also described.
