時間自動機(jī)及其應(yīng)用研究.pdf

1、實時系統(tǒng)在軍事和民用領(lǐng)域都有著廣泛的應(yīng)用，如何保證這類系統(tǒng)的安全性和可靠性是研究人員廣泛關(guān)注的問題。模型檢測方法是分析和驗證實時系統(tǒng)的一種形式化驗證方法，而時間自動機(jī)是模型檢測方法的一個有效工具。時間自動機(jī)是對自動機(jī)理論的擴(kuò)展，提供了形式化的方法來建立和分析實時系統(tǒng)的行為，在模型檢測方面有著重要的應(yīng)用。時間自動機(jī)已經(jīng)成為計算機(jī)科學(xué)理論研究的一個熱點。 帶自動機(jī)是經(jīng)典時間自動機(jī)的一種有窮狀態(tài)構(gòu)造，它的狀態(tài)是由時鐘帶和位置構(gòu)成的偶對

2、，因此如何有效的表示和操作時鐘帶是實現(xiàn)帶自動機(jī)的一個關(guān)鍵問題。目前已經(jīng)提出了幾種有效的表示方法并應(yīng)用于實踐，如DBM、CDD等，DBM是應(yīng)用比較廣泛的一種數(shù)據(jù)結(jié)構(gòu)。本文研究時間自動機(jī)理論及時鐘帶的表示和范式化，主要工作如下： 首先，系統(tǒng)的分析時間自動機(jī)理論及其相關(guān)性質(zhì)，介紹區(qū)域自動機(jī)和帶自動機(jī)。 其次，通過對時鐘帶DBM表示方式的分析，本文分離出一類時鐘帶，針對這類時鐘帶的特點，提出一種DBM的范式化算法。這種范式化算法