A basic parallel process as a parallel pushdown automaton

J.C.M. Baeten, P.J.L. Cuijpers, P.J.A. Tilburg, van

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 15th International Workshop on Expressiveness in Concurrency (EXPRESS'08, Toronto, Canada, August 23, 2008)
EditorsT. Hildebrandt, D. Gorla
Pages35-48
DOIs
Publication statusPublished - 2009

Publication series

NameElectronic Notes in Theoretical Computer Science
Volume242(1)
ISSN (Print)1571-0061

Fingerprint

Dive into the research topics of 'A basic parallel process as a parallel pushdown automaton'. Together they form a unique fingerprint.

Cite this