Two lower bounds for BPA

DOI10.4230/LIPICS.CONCUR.2017.20MaRDI QIDQ5111633zbMATH OpenFDO

Authors Mingzhang Huang, Qiang Yin

Publication date 27 May 2020

zbMATH Keywords

regularitybranching bisimulationBPA

Mathematics Subject Classification ID

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)

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)

Cites work

• scientific article; zbMATH DE number 1222559 (Why is no real title available?)
• scientific article; zbMATH DE number 2155191 (Why is no real title available?)
• scientific article; zbMATH DE number 2086414 (Why is no real title available?)
• scientific article; zbMATH DE number 2086665 (Why is no real title available?)
• BPA bisimilarity is EXPTIME-hard
• Branching bisimilarity of normed BPA processes as a rational monoid
• Branching bisimilarity of normed BPA processes is in NExpTime
• Branching bisimilarity on normed BPA is EXPTIME-complete
• Checking equality and regularity for normed BPA with silent moves
• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• Decidability of bisimulation equivalence for process generating context-free languages
• Decidability of branching bisimulation on normed commutative context-free processes
• Deciding bisimilarity is P-complete
• Equivalence-checking on infinite-state systems: Techniques and results
• Model Checking Probabilistic Timed Automata with One or Two Clocks
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• Process rewrite systems.
• Undecidability of bisimilarity by defender's forcing
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard

Cited in

(7)

• Bisimilarity on basic parallel processes
• Branching bisimilarity of normed BPA processes as a rational monoid
• Branching bisimilarity of normed BPA processes is in NExpTime
• Dyadic lower little BMO estimates
• Uniform random process model revisited
• Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)
• Branching bisimilarity on normed BPA is EXPTIME-complete

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)