Branching bisimilarity on normed BPA is EXPTIME-complete

DOI10.1109/LICS.2015.26zbMATH Open1392.68302arXiv1501.04748MaRDI QIDQ4635802FDOQ4635802

Authors: Chaodong He, Mingzhang Huang 

Publication date: 23 April 2018

Published in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: We put forward an exponential-time algorithm for deciding branching bisimilarity on normed BPA (Bacis Process Algebra) systems. The decidability of branching (or weak) bisimilarity on normed 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. Our result claims that this problem is EXPTIME-complete.

Full work available at URL: https://arxiv.org/abs/1501.04748

Recommendations

• Branching bisimilarity of normed BPA processes is in NExpTime
• Two lower bounds for BPA
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Branching bisimilarity of normed BPA processes as a rational monoid
• Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (9)

• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• Complexity of weak bisimilarity and regularity for BPA and BPP
• Title not available (Why is that?)
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• BPA bisimilarity is EXPTIME-hard
• Branching bisimilarity of normed BPA processes as a rational monoid
• Branching bisimilarity of normed BPA processes is in NExpTime
• Bisimilarity on basic parallel processes

This page was built for publication: Branching bisimilarity on normed BPA is EXPTIME-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635802)