Алгебра Клини

Алгеброй Клини называется алгебра ${\displaystyle {\mathcal {K}}}$ сигнатуры ${\displaystyle \langle 0,1,+,\cdot ,{}^{*}\rangle }$, являющаяся (некоммутативным) идемпотентным полукольцом (с единицей), то есть, удовлетворяющая аксиомам:

• ${\displaystyle a+(b+c)=(a+b)+c}$ (ассоциативность сложения),
• ${\displaystyle a+b=b+a}$ (коммутативность сложения),
• ${\displaystyle a+0=a}$,
• ${\displaystyle a+a=a}$ (идемпотентность сложения),
• ${\displaystyle a(bc)=(ab)c}$ (ассоциативность умножения),
• ${\displaystyle a1=1a=a}$,
• ${\displaystyle a0=0a=0}$,
• ${\displaystyle a(b+c)=ab+ac}$, (левая дистрибутивность),
• ${\displaystyle (a+b)c=ac+bc}$, (правая дистрибутивность),

для которой справедливы также четыре новых аксиомы:

• ${\displaystyle 1+aa^{*}\leqslant a^{*}}$,
• ${\displaystyle 1+a^{*}a\leqslant a^{*}}$,
• ${\displaystyle (ab\leqslant b)\to (a^{*}b\leqslant b)}$,
• ${\displaystyle (ab\leqslant a)\to (ab^{*}\leqslant a)}$,

где частичный порядок ${\displaystyle \leqslant }$ задан эквивалентностью ${\displaystyle a\leqslant b\Leftrightarrow a+b=b}$. Операция «*» называется итерацией или звездой Клини (англ. Kleene star).

Из определения ясно, что алгебра Клини не задана конкретно — это любая алгебра, удовлетворяющая перечисленным аксиомам. То есть, на самом деле, определение задаёт некоторый класс алгебр. Стандартным примером алгебры Клини является алгебра регулярных выражений. При этом, элементами ${\displaystyle {\mathcal {K}}}$ являются множества строк, относительно некоторого фиксированного алфавита ${\displaystyle \Sigma }$, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой ${\displaystyle ab=\{cat(x,y)|x\in a,y\in b\}}$, где ${\displaystyle cat}$ — операция конкатенации строк. Итерация ${\displaystyle a^{*}}$ задаётся как объединение всех множеств ${\displaystyle a^{i}=\underbrace {a\cdot \ldots \cdot a} _{i}}$.

Кроме стандартной интерпретации, существует множество других.

• Dexter Kozen On Kleene algebras and closed semirings. — In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26-47. Springer, 1990. Электронная версия: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps