等價(jià)一致化因子自動(dòng)產(chǎn)生器的算滕及實(shí)現(xiàn).pdf

1、一致化理論在自動(dòng)推理、自然語言理解、邏輯證明、重寫理論等研究領(lǐng)域中有著廣泛的應(yīng)用。目前語法一致化因子的產(chǎn)生算法和工具已經(jīng)相對(duì)成熟，但還沒有產(chǎn)生等價(jià)一致化因子的實(shí)用算法和成熟工具。本文提出并實(shí)現(xiàn)了一種構(gòu)造等價(jià)一致化因子產(chǎn)生器的方案：首先，由淺入深的提出了幾種語法一致化問題的解決方案，本文從最直觀的遞歸方法開始，然后為了避免重復(fù)訪問，新的算法中應(yīng)用了新的數(shù)據(jù)結(jié)構(gòu)-有向無環(huán)圖來表示項(xiàng)，用圖中的有向邊來表示替換。這樣我們可以得到一個(gè)在平均情況下

2、近似于線性的算法。然而此算法依舊可以優(yōu)化，方法就是將項(xiàng)的一致化規(guī)約問題到等價(jià)類的合并問題，并且我們可以在集合的合并中應(yīng)用按秩合并以及路徑壓縮策略，這樣可以使我們的算法在一般情況下更接近線形；再往后，本文又引入等價(jià)一致化的概念，并且將原先語法一致化中問題逐步推廣定義到等價(jià)一致化，并且在等價(jià)一致化中尋找解決方案。為了將語法一致化中的解決方案規(guī)約到等價(jià)一致化，本文的方法是對(duì)相應(yīng)的等價(jià)一致化問題進(jìn)行調(diào)整，把它們轉(zhuǎn)化成幾個(gè)等價(jià)的語法一致化問題的組

3、成的集合。本文中的主要思路是通過項(xiàng)與樹形之間的一一對(duì)應(yīng)關(guān)系以及對(duì)樹形進(jìn)行變換產(chǎn)生對(duì)應(yīng)項(xiàng)的集合，進(jìn)而也就得到了與原先等價(jià)一致化問題等價(jià)的由一些語法一致化問題組成的集合；這樣一來，我們就可以對(duì)此集合中的問題調(diào)用已有的解決方案，也就將語法一致化的解決方案擴(kuò)充到了等價(jià)一致化中。這種方法可以求解通常丟番圖等式所無法得到的等價(jià)一致化因子，因而能夠被廣泛地應(yīng)用于實(shí)際的科學(xué)研究和自動(dòng)工具中去。在模型檢測(cè)這個(gè)研究領(lǐng)域里，目前已有的安全協(xié)議模型檢測(cè)器的核心