1 Search Results for "Huang, Mingzhang"

Document
DOI: 10.4230/LIPIcs.CONCUR.2017.20
Two Lower Bounds for BPA

Authors: Mingzhang Huang and Qiang Yin

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
Branching bisimilarity of normed Basic Process Algebra (nBPA) was claimed to be EXPTIME-hard in previous papers without any explicit proof. Recently it has been pointed out by Petr Jancar that the claim lacked proper justification. In this paper, we develop a new complete proof for the EXPTIME-hardness of branching bisimilarity of nBPA. We also prove that the associated regularity problem of nBPA is PSPACE-hard. This improves previous P-hard result.
Cite as

Mingzhang Huang and Qiang Yin. Two Lower Bounds for BPA. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.CONCUR.2017.20,
  author =	{Huang, Mingzhang and Yin, Qiang},
  title =	{{Two Lower Bounds for BPA}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.20},
  URN =		{urn:nbn:de:0030-drops-77772},
  doi =		{10.4230/LIPIcs.CONCUR.2017.20},
  annote =	{Keywords: BPA, branching bisimulation, regularity}
}
  • Refine by Author
  • 1 Huang, Mingzhang
  • 1 Yin, Qiang

  • Refine by Classification

  • Refine by Keyword
  • 1 BPA
  • 1 branching bisimulation
  • 1 regularity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact