process algebra

process algebra The algebraic study of abstract computing processes. Suppose that there is a set A of basic computational actions (such as assignments, tests, sends, requests), and that these actions can be combined to form finite and infinite processes. There are a number of operations that, given two processes p₁ and p₂, can form new processes; examples are the sequential composition p₁.p₂ and parallel composition p₁||p₂ of the processes. There is a great deal of freedom to define and interpret such operations and the processes they create, especially if the actions and processes may exist concurrently and communicate in various ways. Methods of communication and cooperation between processes are at the heart of process algebra. Process algebra studies semantic ideas using mainly standard algebraic methods, including: axiomatic theories whose axioms are often equations; equivalence relations (e.g. several kinds of bisimulation); algebraic constructions; and computable algebras. An example of a set of axioms for process algebra is the set ACP of J. A. Bergstra and J. W. Klop; this was developed from earlier work on process calculuses by R. Milner and others, and has subsequently been extended and adapted to express the huge range of semantic phenomena exhibited in modern concurrent communicating systems.

The motivation behind process algebra is to model computing systems using processes and to specify the systems by equations based on appropriate operators on processes. Thus concurrent computing systems are specified by equations and their semantics are obtained by solving fixed-point equations. Various related semantic and logical methods are used, including: initial algebra semantics; operational semantics based on transition systems; metric space and topological methods; and modal and temporal logics for reasoning about processes.

Process algebra has the potential to become a general theory of computing, relevant to system modeling and parallel-program development. There is much research needed to develop its foundations, tools, and applications.