




















It has been known since the 60's that any complete discrete $n$-state automaton admits a reset word of length not exceeding $αn^3+o(n^3)$ for some absolute constant $α$. J.-E. Pin and P. Frankl proved this statement with $α=1/6=0.1666...$ in 1982, and this bound remained best known until 2017, when M. Szykuła decreased its value to $α\approx0.1664$. In this note, we present a modification to the latest approach and develop a different counting argument which leads to a more substantial improvement of $α\leqslant 0.1654$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。