克萊尼代數

克萊尼代數（名稱源自美國數學家邏輯學家史蒂芬・科爾・克萊尼）佇咧數學中是下列兩个事物之一 :

帶有滿足德・摩根定律佮無啥相等 _ x _ ∧− _ x _ ≤ _ y _ ∨− _ y _ 的著合 ( 補 ) 運算有界分配格。所以所有的布爾代數攏是 Kleene 代數，但是多數 Kleene 代數毋是布爾代數。親像布爾代數有關於經典命題邏輯，Kleene 代數有關於 Kleene 的三值邏輯。
推廣來源自正是表達式的運算的代數結構。文餘下部份採用這款 Kleene 代數的概念。

定義

佇文獻內底予出著 Kleene 代數和相關結構的各種不等價的定義。攏攬可見 [一]。下跤會出當代上捷用的定義。

Kleene 代數是帶膭有分別寫為 _ a _ + _ b _、_ ab _ 和 _ a _ \ * 的，兩个兩箍運算 + : _ A _ × _ A _ → _ A _ 和・ : _ A _ × _ A _ → _ A _，佮一个函數 \ * : _ A _ → _ A _ 的集合 _ A _，所以滿足下列公理。

+ 和・的結合律 : _ a _ + ( _ b _ + _ c _ )=( _ a _ + _ b _ ) + _ c _ 和 _ a _ ( _ bc _ )=( _ ab _ ) _ c _ 對於 _ A _ 中所有的 _ a _ , _ b _ , _ c _。
+ 的交換律 : _ a _ + _ b _=_ b _ + _ a _ 對於 _ A _ 中所有的 _ a _ , _ b _。
分配律 : _ a _ ( _ b _ + _ c _ )=( _ ab _ ) + ( _ ac _ ) 和 ( _ b _ + _ c _ ) _ a _=( _ ba _ ) + ( _ ca _ ) 對於 _ A _ 中所有的 _ a _ , _ b _ , _ c _。
+ 和・的單位元：對於 _ A _ 中所有的 _ a _ 存在一个 _ A _ 中元素零予得 : _ a _ + 零=零 + _ a _=_ a _。對於 _ A _ 中所有的 _ a _ 存在一个 _ A _ 中元素一使得 : _ a _ 一=一 _ a _=_ a _。
_ a _ 零=零 _ a _=無對著 _ A _ 中所有的 _ a _。

欲寫公理定義一个半環。咱進一步要求 :

+ 是等冪的 : _ a _ + _ a _=_ a _ 對於 _ A _ 中所有的 _ a _。

這馬會當定義佇咧 _ A _ 上的偏序 ≤，通過設定 _ a _ ≤ _ b _ 若是唯一 _ a _ + _ b _=_ b _ ( 抑是等價的 : _ a _ ≤ _ b _ 若是唯一 _ A _ 存在一个 _ x _ 予得 _ a _ + _ x _=_ b _ )。通過這个改序咱會當公式化關於運算 \ * 的最後兩个公理 :

一 + _ a _ ( _ a _ \ * ) ≤ _ a _ \ * 對於 _ A _ 中所有的 _ a _。
一 + ( _ a _ \ * ) _ a _ ≤ _ a _ \ * 對於 _ A _ 中所有的 _ a _。
若是 _ a _ 和 _ x _ 佇咧 _ A _ 著會使 _ ax _ ≤ _ x _，著 _ a _ \ * _ x _ ≤ _ x _。
若是 _ a _ 和 _ x _ 佇咧 _ A _ 著會使 _ xa _ ≤ _ x _，著 _ x _ ( _ a _ \ * ) ≤ _ x _。

佇直覺上，阮應當共 _ a _ + _ b _ 當做 " 並 " 抑是 _ a _ 和 _ b _ 的 " 上細上界 "，和共 _ ab _ 當做某一種單調性的乘法，佇咧 _ a _ ≤ _ b _ 蘊涵 _ ax _ ≤ _ bx _ 的意義上。星號背後的想法是 _ a _ \ *=一 + _ a _ + _ aa _ + _ aaa _ + . . . 對編程理論的觀點，你閣會當共 + 解說所謂 " 選擇 "，共・解說講為 " 順序 "，共 \ * 解說講為 " 重複 "。

例

設 Σ 是有限集合 ( " 字母表 " ) 並設 _ A _ 是佇咧 Σ 上所有正則表達式的集合。咱認為兩个正則表達式是相等的，如果𪜶若是咧講仝款的語言。著 _ A _ 形成一个 Kleene 代數。事實上，這是自由 Kleene 代數，佇正則表達式的任何等式攏對 Kleene 代數的公理會出，並且因此佇所有 Kleene 代數中攏是有效的意義上。

閣再設 Σ 是字母表。設 _ A _ 是佇咧 Σ 上所有正則語言的集合 ( 抑是佇咧 Σ 上所有上下文無關語言的集合；抑是佇咧 Σ 上所有遞歸語言的集合；抑是佇咧 Σ 上所有的語言的集合 )。著 _ A _ 的兩个元素的併集 ( 寫為 + ) 佮串接 ( 寫為・ ) 再次屬於 _ A _，並且 Kleene 星號運算原仔適用佇 _ A _ 的任何元素。咱得著零為空集而一為只包含空字符合的集合的 Kleene 代數 _ A _。

設 _ M _ 是帶著單位元 _ e _ 屘囝半陣，並設 _ A _ 是 _ M _ 的所有的集的集合。對兩个按呢的子集 _ S _ 和 _ T _，設 _ S _ + _ T _ 是 _ S _ 和 _ T _ 的併集並設 _ ST _={ _ st _ : _ s _ ∈ _ S _ ∧ _ t _ ∈ _ T _ }。_ S _ \ * 予人定義做 _ S _ 生成的 _ M _ 彼屘囝半陣，伊會當去予人講 { _ e _ } ∪ _ S _ ∪ _ SS _ ∪ _ SSS _ ∪ . . . 著 _ A _ 變做零為空集來一為 { _ e _ } 的 Kleene 代數。對任何小範圍攏會當進行類似的結構。

準講 _ M _ 是一个集合而且 _ A _ 是佇咧 _ M _ 上所有二箍關係的集合。採用 + 為並，・為著複合，\ * 為自反傳遞噗包 ( hull )，咱就得著矣 Kleene 代數。

帶有運算 ∨ 和 ∧ 的所有的布爾代數成做 Kleene 代數，若是咱對 + 使用 ∨，著・使用 ∧，並對所有的 _ a _ 設立 _ a _ \ *=一。

佇咧算權重有向圖內底的上短路徑的時陣一个非常無仝的 Kleene 代數是有路用的：設 _ A _ 是擴展的實數軸，採用 _ a _ + _ b _ 為 _ a _ 和 _ b _ 的上小者，而且 _ ab _ 是 _ a _ 和 _ b _ 的普通佮 ( 帶有 + ∞ 和-∞ 的佮並定義做 + ∞ )。_ a _ \ * 予人定義對非負 _ a _ 為實數零對負 _ a _ 為-∞。這是紮有零元素 + ∞ 佮一元素是事實素零的 Kleene 代數。

性質

零是上小元素 : 零 ≤ _ a _ 對於 _ A _ 中所有的 _ a _。

_ a _ + _ b _ 的佮是 _ a _ 和 _ b _ 的上細頂界：阮有 _ a _ ≤ _ a _ + _ b _ 和 _ b _ ≤ _ a _ + _ b _ 並且若準 _ x _ 是 _ A _ 的一个元素有咧 _ a _ ≤ _ x _ 和 _ b _ ≤ _ x _，著 _ a _ + _ b _ ≤ _ x _。類似的，_ a _ 一 + . . . + _ a _ n 嘿元素 _ a _ 一 , . . . , _ a _ n 的上細頂界。

乘法佮加法是單調性的：若是 _ a _ ≤ _ b _，著 _ a _ + _ x _ ≤ _ b _ + _ x _、_ ax _ ≤ _ bx _ 和 _ xa _ ≤ _ xb _ 對於 _ A _ 中所有的 _ x _。

關於著 \ * 運算，阮有零 \ *=一和一 \ *=一，\ * 是單調性的 ( _ a _ ≤ _ b _ 蘊涵 _ a _ \ * ≤ _ b _ \ * )，而且 _ a _ n ≤ _ a _ \ * 對所有的自然數 _ n _。進一步的，( _ a _ \ * ) ( _ a _ \ * )=_ a _ \ *、( _ a _ \ * ) \ *=_ a _ \ * 和 _ a _ ≤ _ b _ \ * 若是唯一 _ a _ \ * ≤ _ b _ \ *。

若是 _ A _ 是 Kleene 代數而且 _ n _ 是自然數，則你會當認為講集合 Mn ( _ A _ ) 由帶有 _ A _ 中條目的所有 _ n _ × _ n _ 矩陣構成。使用普通的矩陣加法佮乘法概念，你會當定義一个唯一的 \ *-運算，所以乎 Mn ( _ A _ ) 成做一个 Kleene 代數。

歷史

Kleene 代數毋是 Kleene 定義的；伊介入著正則表達式閣揣一个完備的公理集合來允准佇正則表達式的所有等式的推導。首先約翰・何頓・康威佇正則代數的名義下研究了這个問題。Dexter Kozen 上先證明矣 Kleene 代數的公理解決矣這个問題。

參見

引用