极值同步循环自动机研究

发布时间：2022-02-20 04:10

　　同步自动机是一类很常见且有广泛应用的自动机,关于同步自动机最短同步字长度的Cerny猜想目前是自动机的组合理论领域存留时间最长的公开问题。对于至少有3个状态的自动机,如果Cerny猜想成立,那么极值同步自动机（即最短同步字长度为（n-1）2的n-状态同步自动机）就是同步自动机的极端情形。只有本质字母的极值同步自动机称为极端同步自动机。已知的极端同步自动机只有Cerny自动机Cn（n≥3）和另外8个离散的例子。2006年,A.N.Trahtman基于相关实验提出了如下猜想:不存在未知的极端同步自动机。由于Cerny自动机Cn（n≥3）以及8个极端同步自动机的离散例子之一是循环自动机,可以认为几乎所有已知的极端同步自动机都是循环的。因此,确定极端同步循环自动机将有助于Trahtman猜想乃至Cerny猜想的解决。本文的目标并不局限于确定所有极端同步循环自动机,而是确定所有极值同步循环自动机。本文的主要工作可以划分为如下四个部分:（1）对极值同步循环自动机的亏损字母进行了研究,获取了它们的一些重要特征,并依据这些特征将极值同步循环自动机的亏损字母划分为平分、闭、半闭、开、半开等五种类型。（2... 

【文章来源】：湖南科技大学湖南省

【文章页数】：80 页

【学位级别】：硕士

【部分图文】：

-状态erny自动机Fig.1.1Then-stateernyautomaton

湖南科技大学硕士学位论文-3-例子，其中自动机是J.erny，A.Pirická和B.Rosenauerová于1971年发现的[37]，自动机是J.Kari于2001年发现的[38]，自动机是A.Roman于2008年发现的[39]，自动机是A.N.Trahtman于2006年发现的[36]。图1.1-状态erny自动机Fig.1.1Then-stateernyautomaton图1.2自动机Fig.1.2Theautomaton图1.3自动机Fig.1.3Theautomaton

湖南科技大学硕士学位论文-3-例子，其中自动机是J.erny，A.Pirická和B.Rosenauerová于1971年发现的[37]，自动机是J.Kari于2001年发现的[38]，自动机是A.Roman于2008年发现的[39]，自动机是A.N.Trahtman于2006年发现的[36]。图1.1-状态erny自动机Fig.1.1Then-stateernyautomaton图1.2自动机Fig.1.2Theautomaton图1.3自动机Fig.1.3Theautomaton

【参考文献】：
期刊论文
[1]同步有界偏序自动机[J]. 崔振河,何勇,孙士远.  计算机学报. 2019(03)
[2]拟陷阱同步自动机的最短同步字的长度[J]. 肖芬芳,何勇,胡斌梁,王志喜.  计算机科学. 2012(11)



本文编号：3634287