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

Алгебра Клини — в теоретической информатике, специальная алгебраическая структура, введённая американским математиком Стивеном Клини, являющаяся обобщением алгебры регулярных выражений.

Определение

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

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

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

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

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

Реализации

Из определения ясно, что алгебра Клини не задана конкретно — это любая алгебра, удовлетворяющая перечисленным аксиомам. То есть, на самом деле, определение задаёт некоторый класс алгебр. Стандартным примером алгебры Клини является алгебра регулярных выражений. При этом, элементами $\mathcal{K}$ являются множества строк, относительно некоторого фиксированного алфавита $\Sigma$, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой $ab=\{cat(x,y)|x\in a, y\in b\}$, где $cat$ — операция конкатенации строк. Итерация $a^*$ задаётся как объединение всех множеств $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. Электронная версия: http://www.cs.cornell.edu/~kozen/papers/kacs.ps