License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.17
URN: urn:nbn:de:0030-drops-170809
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17080/
Go to the corresponding LIPIcs Volume Portal

Balasubramanian, A. R.

Complexity of Coverability in Depth-Bounded Processes

pdf-format:
LIPIcs-CONCUR-2022-17.pdf (0.9 MB)

Abstract

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

@InProceedings{balasubramanian:LIPIcs.CONCUR.2022.17,
  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 =		{https://drops.dagstuhl.de/opus/volltexte/2022/17080},
  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
Collection: 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