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

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

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

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

Алгеброй Клини называется алгебра сигнатуры , являющаяся (некоммутативным) идемпотентным полукольцом (с единицей), то есть, удовлетворяющая аксиомам:

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

  • ,
  • ,
  • ,
  • ,

где частичный порядок задан эквивалентностью . Операция «*» называется итерацией или звездой Клини (англ. Kleene star).

Реализации[править | править вики-текст]

Из определения ясно, что алгебра Клини не задана конкретно — это любая алгебра, удовлетворяющая перечисленным аксиомам. То есть, на самом деле, определение задаёт некоторый класс алгебр. Стандартным примером алгебры Клини является алгебра регулярных выражений. При этом, элементами являются множества строк, относительно некоторого фиксированного алфавита , 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой , где — операция конкатенации строк. Итерация задаётся как объединение всех множеств .

Кроме стандартной интерпретации, существует множество других.

Литература[править | править вики-текст]

  • 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