The Complexity of Bisimulation and Simulation on Finite Systems

Moses Ganardi; Stefan Göller; Markus Lohrey

doi:10.23638/LMCS-14(4:5)2018

Moses Ganardi ; Stefan Göller ; Markus Lohrey - The Complexity of Bisimulation and Simulation on Finite Systems

lmcs:4561 - Logical Methods in Computer Science, October 26, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:5)2018

The Complexity of Bisimulation and Simulation on Finite SystemsArticle

Authors: Moses Ganardi ; Stefan Göller ; Markus Lohrey

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. Furthermore, if only one of the input graphs is required to be a tree, the bisimulation (simulation) problem is contained in AC$^1$ (LogCFL). In contrast, it is also shown that the simulation problem is P-complete already for graphs of bounded path-width.

https://doi.org/10.23638/LMCS-14(4:5)2018

Source: arXiv.org:1806.00256

Volume: Volume 14, Issue 4

Secondary volumes: Selected Papers of the 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Published on: October 26, 2018

Accepted on: October 24, 2018

Submitted on: June 4, 2018

Keywords: Computer Science - Logic in Computer Science

Licence: Attribution 4.0 International (CC BY 4.0)