2026-07-23T01:24:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17080 2024-03-06T10:58:42Z ddc:004 open_access

Complexity of Coverability in Depth-Bounded Processes Balasubramanian, A. R. π-calculus Depth-bounded processes Fast-growing complexity classes 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik A. R. Balasubramanian 2022 Is Part Of LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2022.17 urn:nbn:de:0030-drops-170809 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode