when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-170809
URL:

### Complexity of Coverability in Depth-Bounded Processes

 pdf-format:

### 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},
}