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

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

Определяется как алгебра ${\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}}$ в качестве элементов, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой $ab=\{\operatorname {cat} (x,y)|x\in a,y\in b\}$, где $\operatorname {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. Электронная версия: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps