Two lower bounds for BPA
From MaRDI portal
Publication:5111633
DOI10.4230/LIPICS.CONCUR.2017.20zbMATH Open1442.68144MaRDI QIDQ5111633FDOQ5111633
Authors: Mingzhang Huang, Qiang Yin 
Publication date: 27 May 2020
Recommendations
- Branching bisimilarity of normed BPA processes is in NExpTime
- Branching bisimilarity on normed BPA is EXPTIME-complete
- scientific article; zbMATH DE number 2086665
- Complexity of Weak Bisimilarity and Regularity for BPA and BPP
- Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)
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)
Cites Work
- Deciding bisimilarity is P-complete
- Process rewrite systems.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decidability of bisimulation equivalence for process generating context-free languages
- Equivalence-checking on infinite-state systems: Techniques and results
- Title not available (Why is that?)
- On the Ehrenfeucht-Fraïssé game in theoretical computer science
- Model Checking Probabilistic Timed Automata with One or Two Clocks
- Undecidability of bisimilarity by defender's forcing
- Title not available (Why is that?)
- Checking equality and regularity for normed BPA with silent moves
- Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
- Branching Bisimilarity on Normed BPA Is EXPTIME-Complete
- Complexity of Weak Bisimilarity and Regularity for BPA and BPP
- BPA bisimilarity is EXPTIME-hard
- Decidability of branching bisimulation on normed commutative context-free processes
- Title not available (Why is that?)
- Branching Bisimilarity of Normed BPA Processes Is in NEXPTIME
Cited In (4)
This page was built for publication: Two lower bounds for BPA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111633)
