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

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

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

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