| Register Machine Based Processes (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| . We consider the process algebra axiom system ACP extended with two recursive operations: the binary Kleene star , dened by x y = x(x y) + y, and the push-down operation $, dened by x $ y = x((x $ y)(x $ y)) + y. In this setting register machine computation can simply be represented, and an equational theory results that is undecidable. We further show that with branching bisimulation equivalence each computable process can be expressed. With rooted -bisimulation equivalence almost each semi-computable process can be expressed. Finally we show that all -occurrences can be eliminated by using abstraction and auxiliary actions. Key words & Phrases: Concurrency, process algebra, iteration, Kleene star, push-down operation, bisimulation equivalence, expressivity, computability. 1 Introduction In this paper we take as a point of departure the process algebra axiom system ACP(A; ), i.e., the Algebra of Communicating Processes (dened in [BK84]) with actions in set A... | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||