概率纖維化模態(tài)邏輯的計(jì)算復(fù)雜性研究.pdf

1、將不同的邏輯系統(tǒng)進(jìn)行組合,能夠以更加精細(xì)的方式來描述現(xiàn)實(shí)世界。不同的組合技術(shù),如交融(Fusion),直積(Product),纖維化(Fibring)相繼被提出,其中纖維化特別適合于對(duì)模態(tài)邏輯進(jìn)行組合,因此備受關(guān)注。
　　 本文從計(jì)算復(fù)雜性的視角,分析了一大類由正規(guī)模態(tài)邏輯通過纖維組合之后所得到的邏輯系統(tǒng),分別證明了相關(guān)的可滿足性問題的計(jì)算復(fù)雜性。與此同時(shí)本文證明了將兩個(gè)s5系統(tǒng)通過纖維方法進(jìn)行組合后,其中一個(gè)特殊的片段的可滿足

2、性問題的計(jì)算復(fù)雜性是NP-Complete的。本文的另一個(gè)重要貢獻(xiàn)在于,介紹了一種對(duì)模態(tài)邏輯邏輯進(jìn)行概率化的方式,并成功證明了概率化S5邏輯屬于NP-complete,概率纖維化S5邏輯屬于PSPACE-complete。最后本文同樣找出了一個(gè)概率纖維化S5系統(tǒng)的某一個(gè)計(jì)算復(fù)雜性為NP-complete的片段。
　　 這些研究結(jié)果的意義在于,盡管纖維化方法已經(jīng)提出了很長時(shí)間,但是主要的研究工作大多關(guān)注如何使纖維化邏輯的重要性質(zhì)得