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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

Определение

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

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

  • <math>1 + aa^* \leq a^*</math>,
  • <math>1 + a^*a \leq a^*</math>,
  • <math>(ab\leq b)\to (a^*b\leq b)</math>,
  • <math>(ab\leq a)\to (ab^*\leq a)</math>,

где частичный порядок <math>\leq</math>, задан эквивалентностью <math>a\leq b \Leftrightarrow a + b = b</math>. Операция «*» называется итерацией, или звездой Клини (англ. Kleene star).

Реализации

Из определения ясно, что алгебра Клини не задана конкретно — это любая алгебра, удовлетворяющая перечисленным аксиомам. То есть, на самом деле, определение задаёт некоторый класс алгебр. Стандартным примером алгебры Клини является алгебра регулярных выражений. При этом, элементами <math>\mathcal{K}</math> являются множества строк, относительно некоторого фиксированного алфавита <math>\Sigma</math>, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой <math>ab=\{cat(x,y)|x\in a, y\in b\}</math>, где <math>cat</math> — операция конкатенации строк. Итерация <math>a^*</math> задаётся как объединение всех множеств <math>a^i = \underbrace{a\cdot\ldots\cdot a}_i</math>.

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

Литература

  • 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


en:Kleene algebra

fr:Algèbre de Kleene pt:Álgebra de Kleene sr:Klinijeva algebra zh:克莱尼代数

Личные инструменты

Served in 0.071 secs.