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

Определяется как алгебра ${\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}}}$ в качестве элементов, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой ${\displaystyle ab=\{\operatorname {cat} (x,y)|x\in a,y\in b\}}$ , где ${\displaystyle \operatorname {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. Электронная версия: