Abstract
通訊協定是用來指揮協調各電腦之間通訊連接的規定，要確保各通訊協定 的成品是否符合其該有之規格的測試學問，稱之為通訊協定之一致性測試 。事實上，各通訊協定的成品可看做是一個黑盒子，我們將各測試序列輸 入至黑盒子中，觀查其輸出，若輸出符合其規格該有之輸出，則這一個通 訊協定的成品是正確的，反之則此通訊協定的成品是有錯誤的。一個通訊 協定可區分為資料及控制二部分，在此篇論文中，我們只探討通訊協定的 控制部分，此控制部分可用一個有限狀態機來描述。目前已有多種通訊協 定之一致性測試的理論被提出來，其分別是 Transition tours(T) method，Distinguishing sequences(D) method，Characterizing sequences(W) method，Unique input/output(U) method。大部分通訊協 定都存在唯一輸入輸出序列 (Unique input/output sequences; UIO sequences)，並且唯一輸入輸出序列比其它別種測試序列要來得短，也因 此 U 方法在工業界廣被採用。某一個狀態之唯一輸入輸出序列可用來驗 證其狀態之唯一性，其它狀態若輸入別的狀態之唯一輸入輸出序列，將會 得到不同之輸出。 M. Yannakakis 和 D.Lee 已經證明出決定某一個狀態 是否存在唯一輸入輸出序列是一個 PSPACE-complete 的問題，換句話說 ，決定某一個狀態是否存在唯一輸入輸出序列需要花上指數時間，也就因 此我們提出了一個多項式時間之近似演算法，用來找尋某一個狀態之唯一 輸入輸出序列。目前在工業界上，通訊協定的狀態數都非常大，例如 ATM adaptation layer convergence protocol 的狀態數高達 10 的 20 次方，若採用以前 K. Sabnani 或 D. Amer 所提之方法，可能無法應付 。而我們所提之近似演算法可用來解決狀態數大的通訊協定，並且可用來 尋找最低花費之唯一輸入輸出序列(因各通訊協定之各事件所花費的代價 不同)。