Deciding equivalences in simple Process Algebras

Yoram Hirshfeld

Abstract: Bisimulation equivalence is decidable for context free processes (BPA-processes) and for commutative context free processes (BPP). It is decidable in polynomial time for normed BPA-processes and for normed BPP. In contrast, language (trace) equivalence is undecidable for BPP and for BPA-processes.

LFCS report ECS-LFCS-94-294, July 1994.

Previous | Index | Next