Context-Free Processes and Push-Down Processes
Zeno de Hoop

Abstract:
The purpose of this thesis is to examine in which cases context-free processes and push-down processes are the same. In particular, we depart from the well-known case of language-equivalence and instead look at processes using process theory and more fine-grained equivalences, such as bisimulation and contrasimulation. We identify two difficulties when looking at process specifications: head-recursion and transparency. Here, two new results are achieved: we prove that when excluding transparency, context-free processes and push-down processes are equivalent up to at least branching bisimilarity without explicit divergences. When including transparency, we prove that they are equivalent up to at least contrasimulation. Finally, we present a new result where, when one excludes head-recursion and adopts a modified definition of sequential composition, one can improve the equivalence to strong bisimulation. Some of the drawbacks of this modification are discussed as well.