TY - GEN

T1 - A basic parallel process as a parallel pushdown automaton

AU - Baeten, J.C.M.

AU - Cuijpers, P.J.L.

AU - Tilburg, van, P.J.A.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1016/j.entcs.2009.06.012

DO - 10.1016/j.entcs.2009.06.012

M3 - Conference contribution

T3 - Electronic Notes in Theoretical Computer Science

SP - 35

EP - 48

BT - Proceedings of the 15th International Workshop on Expressiveness in Concurrency (EXPRESS'08, Toronto, Canada, August 23, 2008)

A2 - Hildebrandt, T.

A2 - Gorla, D.

ER -