License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6552/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Göller, Stefan ; Lohrey, Markus

On the Parallel Complexity of Bisimulation on Finite Systems

pdf-format:
LIPIcs-CSL-2016-12.pdf (0.5 MB)

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
Collection: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Issue Date: 2016
Date of publication: 29.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI