We investigate the set of basic parallel processes, recursively defined by action prefix, interleaving, 0 and 1. Different from literature, we use the constants 0 and 1 standing for unsuccessful and successful termination in order to stay closer to the analogies in automata theory.
We prove that any basic parallel process is rooted branching bisimulation equivalent to a regular process communicating with a bag (also called a parallel pushdown automaton) and therefore we can regard the bag as the prototypical basic parallel process.
This result is closely related to the fact that any context-free process is either rooted branching bisimulation equivalent or contrasimulation equivalent to a regular process communicating with a stack, a result that is the analogy in process theory of the language theory result that any context-free language is the language of a pushdown automaton.
|Title of host publication||Proceedings of the 15th International Workshop on Expressiveness in Concurrency (EXPRESS'08, Toronto, Canada, August 23, 2008)|
|Editors||T. Hildebrandt, D. Gorla|
|Publication status||Published - 2009|
|Name||Electronic Notes in Theoretical Computer Science|