文章基本信息

标题：On the Parallel Complexity of Bisimulation on Finite Systems
本地全文：下载
作者：Moses Ganardi ; Stefan G{\"o}ller ; Markus Lohrey 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：62
页码：12:1-12:17
DOI：10.4230/LIPIcs.CSL.2016.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：bisimulation; computational complexity; tree width