Title :
Branching Bisimilarity on Normed BPA Is EXPTIME-Complete
Author :
Chaodong He ; Mingzhang Huang
Abstract :
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.
Keywords :
computational complexity; decidability; process algebra; EXPTIME-complete; basic process algebra; branching bisimilarity; decidability; exponential-time algorithm; normed BPA; Algebra; Approximation methods; Computer science; Grammar; Polynomials; Semantics; Syntactics;
Conference_Titel :
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Conference_Location :
Kyoto
DOI :
10.1109/LICS.2015.26
