良結(jié)構(gòu)下推系統(tǒng)的表達能力.pdf

1、良結(jié)構(gòu)下推系統(tǒng)是將狀態(tài)集和棧字符集都擴展為良擬序集的下推系統(tǒng)，它是一個一般化的模型，一個自然的問題是良結(jié)構(gòu)下推系統(tǒng)的表達能力有多強。向量加法系統(tǒng)是一個應用廣泛的模型，本文著重研究向量加法系統(tǒng)的三個擴展系統(tǒng)與良結(jié)構(gòu)下推系統(tǒng)的關(guān)系。本文將向量加法系統(tǒng)的三種擴展系統(tǒng)以及幾個其他模型編碼到了良結(jié)構(gòu)下推系統(tǒng)，這些模型上的許多問題可以歸約到對應的良結(jié)構(gòu)下推系統(tǒng)上的問題。良結(jié)構(gòu)下推系統(tǒng)的表達能力不低于這些模型。
　　本文的主要貢獻有以下三點，通

2、過將導出值的計算轉(zhuǎn)化為順序計算的過程，給出了分支向量加法系統(tǒng)到良結(jié)構(gòu)下推系統(tǒng)的編碼；通過將格局中隱式的棧轉(zhuǎn)化為顯示的棧，給出了遞歸向量加法系統(tǒng)到良結(jié)構(gòu)下推系統(tǒng)的編碼；通過將格局向量的一個維度的信息保存在棧深信息中，給出了一位零測試向量加法系統(tǒng)到良結(jié)構(gòu)下推系統(tǒng)的編碼。相關(guān)的正確性證明也全部給出。以上這三種向量加法系統(tǒng)擴展系統(tǒng)上的可達性問題可以歸約到對應的良結(jié)構(gòu)下推系統(tǒng)上的問題。
　　本文還研究了單計數(shù)器網(wǎng)絡，單計數(shù)器自動機，交替向量