Branching Bisimilarity of Normed BPA Processes is in NEXPTIME
classification
💻 cs.LO
cs.FL
keywords
bisimilarityboundbranchingexponential-timenormedprocessesalgorithmapproach
read the original abstract
Branching bisimilarity on normed BPA processes was recently shown to be decidable by Yuxi Fu (ICALP 2013) but his proof has not provided any upper complexity bound. We present a simpler approach based on relative prime decompositions that leads to a nondeterministic exponential-time algorithm; this is close to the known exponential-time lower bound.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.