同步自動機是一類很常見且有廣泛應(yīng)用的自動機,關(guān)于同步自動機最短同步字長度的Cerny猜想目前是自動機的組合理論領(lǐng)域存留時間最長的公開問題。對于至少有3個狀態(tài)的自動機,如果Cerny猜想成立,那么極值同步自動機（即最短同步字長度為（n-1）2的n-狀態(tài)同步自動機）就是同步自動機的極端情形。只有本質(zhì)字母的極值同步自動機稱為極端同步自動機。已知的極端同步自動機只有Cerny自動機Cn（n≥3）和另外8個離散的例子。2006年,A.N.Trahtman基于相關(guān)實驗提出了如下猜想:不存在未知的極端同步自動機。由于Cerny自動機Cn（n≥3）以及8個極端同步自動機的離散例子之一是循環(huán)自動機,可以認為幾乎所有已知的極端同步自動機都是循環(huán)的。因此,確定極端同步循環(huán)自動機將有助于Trahtman猜想乃至Cerny猜想的解決。本文的目標(biāo)并不局限于確定所有極端同步循環(huán)自動機,而是確定所有極值同步循環(huán)自動機。本文的主要工作可以劃分為如下四個部分:（1）對極值同步循環(huán)自動機的虧損字母進行了研究,獲取了它們的一些重要特征,并依據(jù)這些特征將極值同步循環(huán)自動機的虧損字母劃分為平分、閉、半閉、開、半開等五種類型。（2... 

【文章來源】：湖南科技大學(xué)湖南省

【文章頁數(shù)】：80 頁

【學(xué)位級別】：碩士

【部分圖文】：

-狀態(tài)erny自動機Fig.1.1Then-stateernyautomaton

湖南科技大學(xué)碩士學(xué)位論文-3-例子，其中自動機是J.erny，A.Pirická和B.Rosenauerová于1971年發(fā)現(xiàn)的[37]，自動機是J.Kari于2001年發(fā)現(xiàn)的[38]，自動機是A.Roman于2008年發(fā)現(xiàn)的[39]，自動機是A.N.Trahtman于2006年發(fā)現(xiàn)的[36]。圖1.1-狀態(tài)erny自動機Fig.1.1Then-stateernyautomaton圖1.2自動機Fig.1.2Theautomaton圖1.3自動機Fig.1.3Theautomaton

湖南科技大學(xué)碩士學(xué)位論文-3-例子，其中自動機是J.erny，A.Pirická和B.Rosenauerová于1971年發(fā)現(xiàn)的[37]，自動機是J.Kari于2001年發(fā)現(xiàn)的[38]，自動機是A.Roman于2008年發(fā)現(xiàn)的[39]，自動機是A.N.Trahtman于2006年發(fā)現(xiàn)的[36]。圖1.1-狀態(tài)erny自動機Fig.1.1Then-stateernyautomaton圖1.2自動機Fig.1.2Theautomaton圖1.3自動機Fig.1.3Theautomaton

【參考文獻】：
期刊論文
[1]同步有界偏序自動機[J]. 崔振河,何勇,孫士遠.  計算機學(xué)報. 2019(03)
[2]擬陷阱同步自動機的最短同步字的長度[J]. 肖芬芳,何勇,胡斌梁,王志喜.  計算機科學(xué). 2012(11)



本文編號：3634287