11:24
官方一手arXiv: OpenAI@Yinfeng Zhu
精选
推荐理由：这篇论文用线性代数给出了Černý猜想的一个紧上界，并构造了例子证明最优，对自动机理论很关键。
环形谱下降
共 1 条相关 AI 资讯
7月23日
11:24
论文证明了同步单簇自动机的Černý猜想：若自动机有n个状态，字母a的功能有向图有唯一长度为m的圈C，且a^ℓ将全部状态映射至C（ℓ≥1），则对任意非空真子集S⊂C，存在长度不超过n的词w使得wa^ℓ将C中多于|S|个状态映射到S。由此得到复位词长度上界(m-1)(n-1)+mℓ≤(n-1)²。对任意n≥4，构造了m=2、ℓ=n-2、复位阈值为3n-5的强连通二进制例子，证明该上界是紧的。证明使用了有限维线性代数，下界构造为组合方法。