Branching Bisimilarity on Normed BPA Is EXPTIME-Complete
Chaodong He, Mingzhang Huang · 2015
We put forward an exponential-time algorithm for deciding branching bisimilarity on nor med BPA (Bacis Process Algebra) systems. The decidability of branching bisimilarity on nor med BPA was once a long-standing open problem which was closed by Yuxi Fu. The EXPTIME-hardness is an inference of a slight modification of the reduction presented by Richard Mayr. The result in this paper claims that this problem is EXPTIME-complete.