论文标题
循环自动机和自动机的一组同步单词集的状态复杂性
State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
论文作者
论文摘要
在二进制字母上最缓慢地同步自动机是圆形的，即包含一个单个周期中置换状态的字母，它们的同步单词集具有最大状态的复杂性，这也意味着完整的可及性。我们将更仔细的外观仔细查看，仔细观察了广义的圆形循环和完全可触及的自动机。我们得出的是，在二进制字母上，每个完全可触及的自动机必须是圆形的，这是由于结构性结果表明，该结构结果表明，完全可以在严格的字母上完全可以触及的自动机，而不是始终包含置换字母。我们陈述了足够的条件，即对广义圆形自动机的一组同步单词的状态复杂性是最大的。我们将主要标准应用于自动机的家庭$ \ Mathscr k_n $，该$以前仅猜想拥有此属性。
Most slowly synchronizing automata over binary alphabets are circular, i.e., containing a letter permuting the states in a single cycle, and their set of synchronizing words has maximal state complexity, which also implies complete reachability.Here, we take a closer look at generalized circular and completely reachable automata. We derive that over a binary alphabet every completely reachable automaton must be circular, a consequence of a structural result stating that completely reachable automata over strictly less letters than states always contain permutational letters. We state sufficient conditions for the state complexity of the set of synchronizing words of a generalized circular automaton to be maximal. We apply our main criteria to the family $\mathscr K_n$ of automata that was previously only conjectured to have this property.
