关于同步自动机和Černý猜想的若干研究

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 引 言

1.1 概述

1.2 国内外研究现状

1.3 本文的主要工作和内容安排

第二章 预备知识和研究概况

2.1 有限状态自动机

2.2 自动机的同步性及其检测

2.3 同步自动机的最短同步字

第三章 拟陷阱同步自动机与?erny猜想

3.1 拟陷阱同步自动机的定义和例子

3.2 拟陷阱同步自动机的最短同步字长度的一个上界

3.3 两个注记

第四章C -型同步自动机, n i

4.1 , n i C -型自动机的定义和例子

4.2 模n完全剩余系及其基本性质

4.3 , n i C -型自动机的同步性和最短同步字

第五章 LC-型同步自动机

5.1 轨道及其基本性质

5.2 局部循环均等自动机的定义和例子

5.3 一类特殊的局部循环均等自动机的同步性

第六章 总结与展望

6.1 论文工作总结

6.2 未来工作展望

参考文献

致谢

附录A 攻读学位期间发表论文目录

附录B 攻读学位期间参加研究项目