在二次时间内识别完全可达自动机

《ACM Transactions on Algorithms》：Recognizing Completely Reachable Automata in Quadratic Time

本文提出了解决完全可达有限自动机同步字复杂性的算法，时间复杂度为O(|Σ|?n2)，空间复杂度为O(|Σ|?n)，并证明了弱Don猜想的上界，为该类自动机的同步理论提供了新的算法和界限。

　　

摘要AI 摘要

要查看此由 AI 生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

一个具有状态集 $Q$的完全确定性有限（半）自动机（DFA）是 完全可达的，如果 $Q$ 的每个非空子集都是某个单词作用于 $Q$ 的结果。完全可达自动机的概念特别出现在同步自动机的研究中；该类别包括 ?erny 自动机，并涵盖了几个著名的子类。这一概念由 Bondar 和 Volkov（2016 年）提出，他们还提出了判断一个自动机是否完全可达的复杂性问题。我们开发了一种算法来解决这个问题，该算法的运行时间为 $O(|\Sigma |?n^2)$，空间复杂度为