在过去的几十年里，双仿真已成为一个广泛的范式，应用于并发理论、模型检测、自动机理论、逻辑、编程语言和范畴理论等多个领域。本文探讨了双仿真与数据压缩之间的联系，尤其是与Wheeler自动机（Alanko et al., SODA 2020）之间的关系。
由于标准的双仿真概念并不适用，我们引入了Wheeler双仿真，即尊重所考虑Wheeler自动机的凸结构的双仿真。我们展示了Wheeler相似性会产生一个唯一的最小Wheeler非确定性有限自动机（NFA），这一点与标准双仿真类似。
特别是，在确定性情况下，我们能够恢复给定语言的最小Wheeler确定性自动机。此外，我们还表明，由Wheeler双仿真诱导的最小Wheeler NFA可以在线性时间内构建。这与标准双仿真的情况形成鲜明对比，后者对应的最小NFA构建时间为 $O(m \log n)$（其中 $m$ 为边的数量，$n$ 为状态的数量），需要适应Paige-Tarjan分区细化算法。
与以往的状态减少技术相比，我们的双仿真诱导构造首次实现了(i)获得规范的Wheeler NFA，和(ii)所得到的Wheeler NFA可以在线性时间内构建。
博主点评： 本文的创新之处在于将双仿真与Wheeler自动机结合，提供了一种新的视角来理解自动机的最小化过程。尤其是线性时间构建最小Wheeler NFA的能力，标志着理论计算机科学中的一项重要进展，值得进一步研究与应用。