李旺威, 黎先华

(1. 岭南师范学院数学与统计学院, 广东 湛江 524048; 2. 苏州大学数学科学学院, 江苏 苏州 215006)

Cerny猜想是同步自动机研究的重要问题之一,许多科学技术问题可以用同步自动机模型来解决[2-5]．近年来, 国际上一些著名的群论及半群的专家投入到该问题的研究, 获得了许多创新的成果．2014年, Araújo等[6]证明了本原群同步于每一秩为n-2的变换, 本原群同步于每一秩为2的变换和本原群同步于每一秩为3或4的非一致变换．2019年, Ryzhikov[7]给出无非平凡圈自动机同步字长度的上下界．近年来, Li等[8-9]解决了几乎同步群的两个公开问题, 并证明了非本原群同步于一类非一致变换．本文拟讨论置换群和一个非可逆变换是否可以生成一个常量映射．

1 判断同步半群的方法

若半群〈G,α〉包含一个常量映射, 则称G同步于变换α．若半群的每一个元素都落在一个子群中, 则称该半群是完全正则的．设α∈TnSn和ker(α)={A1,A2,…,Ar}, 则定义α的核类型为[|A1|,|A2|,…,|Ar|]．若半群〈G,α〉是非同步半群, 则存在β∈〈G,α〉G使得半群〈G,β〉完全正则．因此, 完全正则半群在非同步半群中扮演着“堤坝”的角色, 即完全正则半群能阻止生成集生成常量映射, 自然希望能找到一些特殊的元素“打破”这个“堤坝”,首先给出同步链的定义．

设S是Tn的子半群和e∈S．若e2=e,则称e是S的幂等元, 且记E(S)={x∈S:x2=x}．设Y={a1,a2,…,at}是集合Xn的子集,e是Tn的幂等元, 且满足aie=a(ai,a=at∈Y)和xe=x(x∈XnY), 记为e=[a1,a2,…,at], 其中at=a．

设ei=[ai1,ai2,…,ait](i=1,2,…,r)．对于幂等元ei, 若非单点核类是一个同步链,则称集合E={e1,e2,…,er}具有性质SYN．由于e1e2…er是一个常量映射, 则半群S是同步的．因此, 若E(S)包含一个具有性质SYN的子集E,则该半……