WikiSort.ru - Не сортированное

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

Определение

Алгеброй Клини называется алгебра ${\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

Это заготовка статьи по алгебре. Вы можете помочь проекту, дополнив её.

Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.