完備交互模型上的計(jì)算理論研究.pdf

1、進(jìn)程演算從20世紀(jì)80年代Milner的CCS交互模型開(kāi)始已有30年光景.期間成百上千的模型和等價(jià)關(guān)系被提出來(lái)，研究也深入了相關(guān)的各個(gè)分支。但是在完備交互模型上研究計(jì)算理論是一個(gè)還未深入研究的方向。對(duì)于這個(gè)方向首先面臨的問(wèn)題是定義合適的完備模型。絕對(duì)等價(jià)在完備模型中是個(gè)重要的概念，它和傳統(tǒng)的外部等價(jià)是否一致也是一個(gè)有趣且重要的問(wèn)題。這個(gè)問(wèn)題的解決有助于對(duì)互模擬等價(jià)關(guān)系的進(jìn)一步理解，更重要的是它能幫助證明一個(gè)模型是否是完備的。在絕對(duì)等價(jià)和

2、外部等價(jià)的一致性問(wèn)題上已經(jīng)有一些結(jié)果。如果在語(yǔ)言中包含加操作符，那么一致性就相對(duì)較容易證明，反之，會(huì)變得很困難。實(shí)際上對(duì)在沒(méi)有加操作符的語(yǔ)言上的一致性已經(jīng)作為公開(kāi)問(wèn)題。
　　加操作符有強(qiáng)大的觀察能力而絕對(duì)等價(jià)又是從觀察角度定義的，所以我們可以用加操作符來(lái)迫使一個(gè)進(jìn)程做一連串特定的動(dòng)作。當(dāng)沒(méi)有加操作符的時(shí)候模型會(huì)變得簡(jiǎn)單。一個(gè)模型越簡(jiǎn)單它的觀察能力就越弱，于是證明一致性就更難。但是當(dāng)模型足夠簡(jiǎn)單時(shí)，特別地，當(dāng)它是有限模型時(shí)，我們可以