時間自動機可達性研究.pdf

1、實時系統(tǒng)的模型檢驗方法是一種保證計算機實時系統(tǒng)安全性和可靠性的嚴格的形式化方法,隨著計算機科學(xué)的發(fā)展,這種方法已經(jīng)被廣泛地接受和使用.由于模型檢驗方法在對系統(tǒng)建模時存在狀態(tài)空間爆炸問題,因此模型驗證核心問題是狀態(tài)空間最小化問題.使用時間自動機對實時系統(tǒng)規(guī)范和驗證,主要包括對實時系統(tǒng)建模即構(gòu)造系統(tǒng)的時間自動機和安全可靠性驗證.這兩方面的核心問題是狀態(tài)空間的簡化和狀態(tài)可達性分析.而這一核心問題是本文研究的重點.在實時系統(tǒng)規(guī)范驗證中.考慮到系

2、統(tǒng)中多數(shù)待檢驗問題僅僅是一些簡單的性質(zhì).因此我們不必構(gòu)造系統(tǒng)的所有狀態(tài)集合,而僅僅考慮對可達性問題的判斷.論文對時間自動機的可達性問題進行了深入研究,對不同的可達性分析方法進行了比較,并著重對基于時間約束的可達性分析方法進行分析.在此基礎(chǔ)上,針對基于時間約束的可達性分析方法,本文給出了該方法的機器表示,并提出了一種新的后繼計算方法,通過該方法能夠較好地減少后繼狀態(tài)空間的個數(shù),從而使問題規(guī)模減小;另外給出了可達性算法的預(yù)處理方法,通過預(yù)處