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

Алгебра Кліні - в теоретичної інформатики, спеціальна алгебраїчна структура, введена американським математиком Стівеном Кліні, що є узагальненням алгебри регулярних виразів.


Визначення

Алгеброю Кліні називається алгебра \ 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


Інформатика Це заготовка статті по інформатиці. Ви можете допомогти проекту, виправивши або дописавши її.