Алгебра Клини — специальная алгебраическая структура, введённая Стивеном Клини как обобщение алгебры регулярных выражений; широко используется в теоретической информатике.
Определяется как алгебра сигнатуры , являющаяся (некоммутативным) идемпотентным полукольцом (с единицей), то есть, удовлетворяющая аксиомам: (ассоциативность сложения), (коммутативность сложения), , (идемпотентность сложения), (ассоциативность умножения), , , , (левая дистрибутивность), , (правая дистрибутивность), для которой справедливы также четыре новых аксиомы: , , , , где частичный порядок задан эквивалентностью . Операция «*» называется итерацией или звездой Клини ().
Алгебра регулярных выражений — стандартный пример алгебры Клини: со множествами строк (над некоторым фиксированным алфавитом) в качестве элементов, 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. Электронная версия: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps
Категория:Формальные языки