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 -