クリーネ圏（Kleene圏）の定義

トレース付き双デカルト・モノイド圏 - 檜山正幸のキマイラ飼育記 メモ編とかKozen圏 - 檜山正幸のキマイラ飼育記 メモ編にも書いてあるが、もとネタから念のため引き写しておく。

---

Kahl "Refactoring Heterogeneous Relation Algebras around Ordered Categories and Converse" Published on December 10, 2004→http://www.cosc.brocku.ca/Faculty/Winter/JoRMiCS/Vol1/PDF/v1n12.pdf 18p 4.2節

まず引用：

Definition 34. An idempotent semiring category (ISR category) is an upper semilattice categories with zero morphisms.

r:A→A, q:B→A、s:A→Cに対して：

1. ISR圏である。
2. End(X)には*が割り当ててある。
3. r* = 1 + r + r*;r*
4. q;r⊆q ⇒ q;r* ⊆q
5. r;s⊆s ⇒ r*;s ⊆s

---

木下「不動点をめぐる代数構造たち」2001, 2004 →http://unit.aist.go.jp/cvs/tr-data/PS02-005.PDF

q:A→A, r, x:X→A、s, y:A→Yに対して：

1. homsetが半束である。
2. 結合（合成）が半束の射である。
3. q:A→A, r, x:A→Bに対して：1 + q*;q = q*
4. 1 + q;q* = q*
5. r + x;q ⊆x ⇒ r;q*⊆x
6. s + q;y ⊆y ⇒ q*;s⊆y

原論文では、q:A→A, r, x:A→Bに対して、r + x;q ⊆x ⇒ r;q*⊆x、r + q;x ⊆x ⇒ q*;r⊆x となっているが、間違いだろう。

---

Hopkins "Kleene Categories" September, 2001→http://www.chimaira.org/archive/KleeneCat.txt

A Kleene Category C is a category in which

(A) Every homset C(A,B) is partially ordered such that every finite

    subset has a least upper bound.

(B) If U1, U2 are finite subsets of C(A2,A3) and C(A1,A2) then

    sup(U1) sup(U2) = sup(U1 U2)

(C) There is an operation f |-> f* defined over each homset C(A,A),

    such that:

                1_A + f f* <= f*

                if u + xv + wx <= x then w* u v* <= x
where in the latter inequality, u: A -> B, v: A -> A, w: B -> B, x: A -> B.

---

Kozen "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events (1994)" →http://citeseer.ist.psu.edu/kozen94completeness.html

非自明な公理：

• 1 + a・a* ≦ a*
• 1 + a*・a ≦ a*

• b + a・x ≦ x ⇒ a*・b ≦ x
• b + x・a ≦ x ⇒ b・a* ≦ x