| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 426670 | Information and Computation | 2009 | 18 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
