主題
Search

Critical Pair


x->yu->v項重寫系統的兩個規則,並假設這些規則沒有共同的變數。如果它們有,則重新命名變數。如果 x_1x 的子項(或項 x 本身),使得它不是變數,並且對 (x_1,u)可合一的,具有最通用的合一器 theta,則 ytheta 和透過用 vtheta 替換 xtheta 中的 x_1theta 而得到的結果被稱為臨界對。

一個項重寫系統的所有臨界對都是可連線的(即可簡化為相同的表示式)這一事實,意味著該系統是區域性合流的。

例如,如果 f(x,x)->xg(f(x,y),x)->h(x),則 g(x,x)h(x) 將形成一個臨界對,因為它們都可以從 g(f(x,x),x) 匯出。

請注意,臨界對有可能由一個規則產生,以兩種不同的方式使用。例如,在字串重寫中"AA" -> "B",臨界對 ("BA", "AB") 是將一個規則應用於"AAA"以兩種不同方式的結果。


另請參閱

Church-Rosser Property, Confluent, Finitely Terminating, Knuth-Bendix Completion Algorithm, Reduction Order, Term Rewriting System

本條目的部分內容由 Todd Rowland 貢獻

本條目的部分內容由 Alex Sakharov (作者連結) 貢獻

使用 探索

參考文獻

Baader, F. and Nipkow, T. Term Rewriting and All That. Cambridge, England: Cambridge University Press, 1999.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1037, 2002.

在 上被引用

Critical Pair

請引用為

Rowland, Todd; Sakharov, Alex; 和 Weisstein, Eric W. "Critical Pair." 來自 Web 資源。 https://mathworld.tw/CriticalPair.html

主題分類