摘要：自動(dòng)機(jī)的重置序列也稱為同步序列,具有以下特性:有限自動(dòng)機(jī)通過運(yùn)行重置序列w,可從任意一個(gè)未知的或無法觀測到的狀態(tài)q0到達(dá)某個(gè)特定狀態(tài)qw。這僅依賴于w,而與開始運(yùn)行w時(shí)的狀態(tài)q0無關(guān)。這一特性可用于部分可觀察的復(fù)雜系統(tǒng)的自動(dòng)恢復(fù),而無需重啟,甚至有時(shí)不能重啟?；诖?重置問題自出現(xiàn)以來便得到關(guān)注和持續(xù)研究。最近幾年,它被擴(kuò)展到可以描述諸如分布式、嵌入式實(shí)時(shí)系統(tǒng)等復(fù)雜系統(tǒng)的無限狀態(tài)模型上,比如時(shí)間自動(dòng)機(jī)和寄存器自動(dòng)機(jī)等。以時(shí)間自動(dòng)機(jī)的重置問題的計(jì)算復(fù)雜性為研究對象,發(fā)現(xiàn)重置問題與可達(dá)性問題有著緊密的聯(lián)系。主要貢獻(xiàn)是:(1)利用時(shí)間自動(dòng)機(jī)可達(dá)性問題的最新成果,完善完全的確定的時(shí)間自動(dòng)機(jī)重置問題的計(jì)算復(fù)雜性結(jié)論;(2)對部分規(guī)約的確定的時(shí)間自動(dòng)機(jī),研究得出,即使在輸入字母表大小減至2的情況下,其復(fù)雜性仍是PSPACE-完全的;特別地,在單時(shí)鐘情況下是NLOGSPACE-完全的;(3)對完全的非確定的時(shí)間自動(dòng)機(jī),研究得出其Di-可重置問題(i=1,2,3)是不可判定的,其重置問題與非確定的寄存器自動(dòng)機(jī)重置問題在指數(shù)時(shí)間可以相互歸約,通過證明指數(shù)時(shí)間歸約相對高復(fù)雜性類具有封閉性,利用非確定的寄存器自動(dòng)機(jī)的結(jié)論得出單時(shí)鐘的時(shí)間自動(dòng)機(jī)的重置問題是Ackermann-完全的、限界的重置問題是NEXPTIME-完全的。這些復(fù)雜性結(jié)論,說明關(guān)于時(shí)間自動(dòng)機(jī)的重置問題大都是難解的,一方面,為時(shí)間系統(tǒng)的可重置性的檢測和求解奠定堅(jiān)實(shí)的理論基礎(chǔ),另一方面,為以后尋找具有高效算法的特殊結(jié)構(gòu)的時(shí)間系統(tǒng)(即具有高效算法的問題子類)給予理論指導(dǎo)。