Imperative process algebra and models of parallel computation (Q6580081)

At first, an imperative process algebra is recalled. It is based on the algebra of communicating processes (ACP), which is enriched with silent steps \(\tau\) and \(\epsilon\) indicating an empty process. The resulting formalism, denoted as \(\mathrm{ACP}_\epsilon^\tau\), is subsequently further enriched with features to communicate data between processes, to change data involved in the course of a process, and to proceed at certain stages of a process in a way that depends on the changing data (\(\mathrm{ACP}_\epsilon^\tau\)-I). Later this formalism is extended with recursion data (\(\mathrm{ACP}_\epsilon^\tau\)-I+REC) and with cluster fair abstraction rule (\(\mathrm{ACP}_\epsilon^\tau\)-I+REC+CFAR) and some properties are shown. As the paper's main contribution, relations between these process algebras and various RAMP (random access machine process) models of computation are presented (asynchronous parallel RAMP model, synchronous parallel RAMP model). Complexity issues are studied as well.