Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Ganardi, Moses; Göller, Stefan; Lohrey, Markus http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-65522
URL:

; ;

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: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI