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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

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

  • 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