Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Balasubramanian, A. R. License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-170809

Complexity of Coverability in Depth-Bounded Processes



We consider the class of depth-bounded processes in π-calculus. These processes are the most expressive fragment of π-calculus, for which verification problems are known to be decidable. The decidability of the coverability problem for this class has been achieved by means of well-quasi orders. (Meyer, IFIP TCS 2008; Wies, Zufferey and Henzinger, FoSSaCS 2010). However, the precise complexity of this problem has not been known so far, with only a known EXPSPACE-lower bound.
In this paper, we prove that coverability for depth-bounded processes is 𝐅_ε₀-complete, where 𝐅_ε₀ is a class in the fast-growing hierarchy of complexity classes. This solves an open problem mentioned by Haase, Schmitz, and Schnoebelen (LMCS, Vol 10, Issue 4) and also addresses a question raised by Wies, Zufferey and Henzinger (FoSSaCS 2010).

BibTeX - Entry

  author =	{Balasubramanian, A. R.},
  title =	{{Complexity of Coverability in Depth-Bounded Processes}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-170809},
  doi =		{10.4230/LIPIcs.CONCUR.2022.17},
  annote =	{Keywords: \pi-calculus, Depth-bounded processes, Fast-growing complexity classes}

Keywords: π-calculus, Depth-bounded processes, Fast-growing complexity classes
Seminar: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI