Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2022/17080/
Balasubramanian, A. R.
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},
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 | |
| Seminar: | 33rd International Conference on Concurrency Theory (CONCUR 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 06.09.2022 |
