Undecidable equivalences for basic parallel processes

摘要

The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that all the preorders and equivalences except bisimulation in Glabbeek's linear time-branching time spectrum are undecidable for BPP. The results are obtained by extending Hirshfeld's encoding of Minsky machines into BPP. We also show that those preorders and equivalences are undecidable even for a restriction of BPP to 2-labels.