主題
Search

歸約系統


在一個系統中,根據有限的重寫規則,形式語言的詞語(表示式)可以被轉換,這樣的系統被稱為歸約系統。雖然歸約系統也稱為字串重寫系統項重寫系統,但術語“歸約系統”更通用。

Lambda 演算是一個歸約系統的例子,其中lambda 轉換規則構成了其重寫規則。

如果歸約系統的任何重寫規則都不適用於表示式 E,則稱 E 對於該歸約系統處於正規化。

如果表示式對 (x,y) 中的 xy 都可以透過零個或多個歸約步驟(即,重寫規則的應用)歸約到相同的表示式,則稱該表示式對是可連線的。

如果 x 在一步中歸約到 y,則表示為 x->y。如果 x 在零個或多個步驟中歸約到 y,則表示為 x->_*y。如果存在一個序列 {a_0,...,a_n} 使得 a_0=xa_n=y,並且對於每一對 (a_i,a_(i+1)),要麼 a_i->a_(i+1) 要麼 a_(i+1)->a_i,則使用符號 x<->_*y


另請參閱

Church-Rosser 屬性, 合流, 臨界對, 有限終止, 形式語言, Knuth-Bendix 完成演算法, Lambda 演算, 多向系統, 歸約順序, 字串重寫系統

此條目由 Alex Sakharov 貢獻 (作者連結)

使用 探索

參考文獻

Baader, F. and Nipkow, T. 項重寫及其相關內容。 Cambridge, England: Cambridge University Press, 1999.

在 中被引用

歸約系統

請這樣引用

薩哈羅夫,亞歷克斯. "歸約系統." 來自 Web 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/ReductionSystem.html

主題分類