一句话：确定了树、项及有界路径宽图上互模拟与模拟问题的精确复杂度分界。
本文研究受限图类上（互）模拟问题的计算复杂度。作者针对树以指针结构或项表示的情形，证明（互）模拟问题分别对对数空间或 NC^1 完全，解决了 Balcázar、Gabarró 与 Sántha 提出的开放问题；若仅要求一个输入图是树，则互模拟问题属于 AC^1，模拟问题属于 LogCFL。相反，对于有界路径宽的图，模拟问题已是 P-完全。该方法通过精细的图类归约与复杂度类刻画，给出了树、项与有界路径宽图之间复杂度的完整分界。
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.
@article{paperbot366,
title = {The Complexity of Bisimulation and Simulation on Finite Systems},
author = {Moses Ganardi and Stefan Göller and Markus Lohrey},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 4},
year = {2018},
doi = {10.23638/lmcs-14(4:5)2018}
}