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

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

Определяется как алгебра $𝒦$ сигнатуры $⟨0,1,+,\cdot ,{}^{*}⟩$, являющаяся (некоммутативным) идемпотентным полукольцом (с единицей), то есть, удовлетворяющая аксиомам:

• $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+a{a}^{*}⩽a^{*}$,
• $1+a^{*}a⩽a^{*}$,
• $(ab⩽b)\to (a^{*}b⩽b)$,
• $(ab⩽a)\to (a{b}^{*}⩽a)$,

где частичный порядок $⩽$ задан эквивалентностью $a⩽b\iff a+b=b$. Операция «*» называется итерацией или звездой Клини (Шаблон:Lang-en).

Алгебра регулярных выражений — стандартный пример алгебры Клини: со множествами строк (над некоторым фиксированным алфавитом) $𝒦$ в качестве элементов, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой $ab=\{\mathrm{cat}(x,y)|x\in a,y\in b\}$, где $\mathrm{cat}$ — операция конкатенации строк. Итерация $a^{*}$ задаётся как объединение всех множеств $a^i=\underset{i}{\underbrace{a\cdot \dots \cdot a}}$.

Литература

• 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