2026-08-10T07:29:24Z https://drops.dagstuhl.de/oai

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

On the Parallel Complexity of Bisimulation on Finite Systems Ganardi, Moses Göller, Stefan Lohrey, Markus bisimulation computational complexity tree width In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC^1, respectively. This solves an open problem from Balcázar, Gabarró, and Sántha. We also show that the simulation problem is P-complete even for graphs of bounded path-width. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Stefan Göller and Markus Lohrey 2016 Is Part Of LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2016.12 urn:nbn:de:0030-drops-65522 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.12 eng https://creativecommons.org/licenses/by/3.0/legalcode