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

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

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