论文部分内容阅读
同步自动机是一种特殊的有限状态自动机，在机器人学、工业自动化以及生物计算等方面有重要应用，同步性检测和最短同步字的长度（特别是（?）ern（?）猜想）是同步自动机理论研究的两个核心问题。研究同步自动机的常用方法是按照同步自动机的结构特征进行分类，然后分析各类同步自动机的同步性检测问题，或者求解它们的最短同步字的长度，从而验证它们是否满足（?）ern（?）猜想。本文对拟陷阱同步自动机、Cn,i-型同步自动机和LC-型同步自动机进行了研究。对于任意一个拟陷阱同步自动机，利用它的强连通子自动机的状态数，给出了它的最短同步字的长度的一个上界，进而获得了它满足（?）ern（?）猜想的一系列充分条件。对于任意一个Cn,i-型自动机，利用模完全剩余系的特性，给出了它满足同步性的一个充分与必要条件，并且在它具有同步性时确定了它的最短同步字。对于任意一个LC-型同步自动机，通过分析它的同构自动机LCA的同步性，证明了LC-型同步自动机满足（?）ern（?）猜想。