Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2016.12
URN: urn:nbn:de:0030-drops-65522
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6552/
Ganardi, Moses ; Göller, Stefan ; Lohrey, Markus
On the Parallel Complexity of Bisimulation on Finite Systems
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{ganardi_et_al:LIPIcs:2016:6552,
author = {Moses Ganardi and Stefan G{\"o}ller and Markus Lohrey},
title = {{On the Parallel Complexity of Bisimulation on Finite Systems}},
booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
pages = {12:1--12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-022-4},
ISSN = {1868-8969},
year = {2016},
volume = {62},
editor = {Jean-Marc Talbot and Laurent Regnier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6552},
URN = {urn:nbn:de:0030-drops-65522},
doi = {10.4230/LIPIcs.CSL.2016.12},
annote = {Keywords: bisimulation, computational complexity, tree width}
}
| Keywords: | bisimulation, computational complexity, tree width | |
| Seminar: | 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 29.08.2016 |
