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

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

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