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

lmcs:4561 - Logical Methods in Computer Science, October 26, 2018, Volume 14, Issue 4
The Complexity of Bisimulation and Simulation on Finite Systems

Authors: Ganardi, Moses and Göller, Stefan and Lohrey, Markus

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\'azar, Gabarr\'o, and S\'antha. 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.

Source : oai:arXiv.org:1806.00256
DOI : 10.23638/LMCS-14(4:5)2018
Volume: Volume 14, Issue 4
Published on: October 26, 2018
Submitted on: June 4, 2018
Keywords: Computer Science - Logic in Computer Science

Version2

Consultation statistics

This page has been seen 33 times.