In der Mathematik, eine Algebra von Kleene (genannt nach Stephen Cole Kleene) ist irgendein zwei verschiedener Dinge:

• Ein begrenztes verteilendes Gitter mit einer Involution, die die Gesetze von De Morgan (d. h. eine Algebra von De Morgan) zusätzlich befriedigt, die Ungleichheit x−x  y−y befriedigend. Kleene (und De Morgan) Algebra sind Unterklassen von Algebra von Ockham. Die einfachste Algebra von Kleene dieser Art ist der drei geschätzte LogikK3 von Kleene. (Das ist der Logik von Boolean analog, die die einfachste Algebra von Boolean ist.)
• Eine algebraische Struktur, die die von regelmäßigen Ausdrücken bekannten Operationen verallgemeinert. Der Rest dieses Artikels befasst sich mit diesem Begriff der Algebra von Kleene.

Definition

Verschiedene inequivalent Definitionen von Algebra von Kleene und verwandten Strukturen sind in der Literatur gegeben worden. Sieh [1] für einen Überblick. Hier werden wir die Definition geben, die scheint, heutzutage am üblichsten zu sein.

Eine Kleene Algebra ist ein Satz zusammen mit zwei binären Operationen +: × ein  A und ·: × ein  A und eine Funktion *: Ein  A, schriftlich als + b, ab und a* beziehungsweise, so dass die folgenden Axiome zufrieden sind.

• Associativity + und ·: + (b + c) = (+ b) + c und (bc) = (ab) c für den ganzen a, b, c in A.
• Commutativity +: + b = b + für den ganzen a, b in Einem
• Distributivity: (b + c) = (ab) + (ac) und (b + c) = (ba) + (ca) für den ganzen a, b, c in Einem
• Identitätselemente für + und ·: Dort besteht ein Element 0 in Einem solchem dass für alle in A: + 0 = 0 + = a. Dort besteht ein Element 1 in Einem solchem dass für alle in A: a1 = 1a = a.
• a0 = 0a = 0 für alle in A.

Die obengenannten Axiome definieren einen Halbring. Wir verlangen weiter:

• + ist idempotent: + = für alle in A.

Es ist jetzt möglich, eine teilweise Ordnung  auf durch das Setzen eines  b wenn und nur wenn + b = b zu definieren (oder gleichwertig: Ein  b wenn, und nur wenn dort ein x in Einem solchem dass + x = b) besteht. Mit dieser Ordnung können wir die letzten zwei Axiome über die Operation * formulieren:

• 1 + (*)  a* für alle in A.
• 1 + (*) ein  a* für alle in A.
• wenn a und x in Einem solchem dass Axt  x, dann a*x  x sind
• wenn a und x in Einem solchem dass xa  x, dann x (*)  x sind

Intuitiv sollte man + b als die "Vereinigung" oder "am wenigsten ober gebunden" a und b und von ab als etwas Multiplikation denken, die im Sinn monotonisch ist, dass ein  b Axt  bx einbezieht. Die Idee hinter dem Sternmaschinenbediener ist a* = 1 + + aa + aaa +... Von der Einstellung der Programmiersprache-Theorie kann man auch + als "Wahl" dolmetschen, · als "sequencing" und * als "Wiederholung".

Beispiele

Lassen Sie Σ ein begrenzter Satz (ein "Alphabet") sein und A der Satz aller regelmäßigen Ausdrücke über Σ sein zu lassen. Wir betrachten zwei solche regelmäßigen Ausdrücke als gleich, wenn sie dieselbe Sprache beschreiben. Dann Formen eine Algebra von Kleene. Tatsächlich ist das eine freie Algebra von Kleene im Sinn, dass jede Gleichung unter regelmäßigen Ausdrücken aus den Algebra-Axiomen von Kleene folgt und deshalb in jeder Algebra von Kleene gültig ist.

Lassen Sie wieder Σ ein Alphabet sein. Lassen Sie A der Satz aller regelmäßigen Sprachen über Σ sein (oder der Satz aller Sprachen ohne Zusammenhänge über Σ; oder der Satz aller rekursiven Sprachen über Σ; oder der Satz aller Sprachen über Σ). Dann die Vereinigung (schriftlich als +) und die Verkettung (schriftlich als ·) zwei Elemente dessen gehören wieder A, und tut so die auf jedes Element von A angewandte Sternoperation von Kleene. Wir erhalten eine Algebra von Kleene mit 0, der leere Satz und 1 seiend, der Satz seiend, der nur die leere Schnur enthält.

Lassen Sie M ein monoid mit dem Identitätselement e sein und A der Satz aller Teilmengen der M sein zu lassen. Für zwei solche Teilmengen S und T, lassen Sie S + T die Vereinigung von S und T sein und ST = {der St. zu setzen: s in S und t in T\. S* wird definiert, weil der submonoid der M durch S erzeugt hat, der als {e}  S  SS  SSS  beschrieben werden kann... Dann Formen eine Algebra von Kleene mit 0, der leere Satz und 1 seiend {e} seiend. Ein analoger Aufbau kann für jede kleine Kategorie durchgeführt werden.

Nehmen Sie an, dass M ein Satz ist und A der Satz aller binären Beziehungen auf der M Einnahme + ist, um die Vereinigung zu sein, · um die Zusammensetzung und * zu sein, um der reflexive transitive Rumpf zu sein, erhalten wir eine Algebra von Kleene.

Jede Boolean Algebra mit Operationen und verwandelt sich in eine Algebra von Kleene, wenn wir für +, dafür verwenden · und Satz a* = 1 für den ganzen a.

Eine ziemlich verschiedene Algebra von Kleene ist nützlich, wenn sie kürzeste Pfade in belasteten geleiteten Graphen schätzt: Lassen Sie A die verlängerte Linie der reellen Zahl sein, + b zu nehmen, um das Minimum von a und b und ab zu sein, um die gewöhnliche Summe von a und b (mit der Summe +  und  zu sein, der als +  wird definiert). a* wird definiert, um die Null der reellen Zahl für nichtnegativen a und der  für negativen a zu sein. Das ist eine Algebra von Kleene mit dem Nullelement +  und einem Element die Null der reellen Zahl.

Eigenschaften

Null ist das kleinste Element: 0  für alle in A.

Die Summe + b ist das am wenigsten obere, das a und b gebunden ist: Wir haben einen  + b und b  + b, und wenn x ein Element mit einem  x und b  x, dann + b  x ist. Ähnlich +... + des am wenigsten oberen zu sein, hat der Elemente a..., a gebunden.

Multiplikation und Hinzufügung sind monotonisch: wenn ein  b, dann + x  b + x, Axt  bx und xa  xb für den ganzen x in A.

Bezüglich * Operation haben wir 0* = 1 und 1* = 1, das * ist monotonisch (ein  bezieht b a*  b * ein), und dass ein  a* für jede natürliche Zahl n. Außerdem, (*) (*) = *, (*)* = *, und ein  b* wenn und nur wenn a*  b*.

Wenn A eine Algebra von Kleene ist und n eine natürliche Zahl ist, dann kann man den Satz als M (A) betrachten, aus dem ganzen n-by-n matrices mit Einträgen in A bestehend.

Mit den gewöhnlichen Begriffen der Matrixhinzufügung und Multiplikation kann man einen einzigartigen *-operation definieren, so dass M (A) eine Algebra von Kleene wird.

Geschichte

Algebra von Kleene wurden von Kleene nicht definiert; er hat regelmäßige Ausdrücke eingeführt und hat um einen ganzen Satz von Axiomen gebeten, die Abstammung aller Gleichungen unter regelmäßigen Ausdrücken erlauben würden. Das Problem wurde zuerst von John Horton Conway unter dem Namen von regelmäßigen Algebra studiert. Die Axiome von Algebra von Kleene beheben dieses Problem, wie zuerst von Dexter Kozen gezeigt wurde.

1. Dexter Kozen: Auf Kleene Algebra und geschlossenen Halbringen. In Rovan, Redakteur, Proc. Mathematik. Gefunden. Comput. Sci. Band 452 von Vortrag-Zeichen in der Informatik, Seiten 26-47. Springer, 1990. Online an

http://www.cs.cornell.edu/~kozen/papers/kacs.ps

1. Dexter Kozen: CS786 Frühling 04, Einführung in die Kleene Algebra.

http://www.cs.cornell.edu/Courses/cs786/2004sp/

1. J.H. Conway, Regelmäßige Algebra und begrenzte Maschinen, Chapman und Saal, 1971, internationale Standardbuchnummer 0-412-10620-5. Junge. IV.

Siehe auch

• Handlungsalgebra
• Algebraische Struktur
• Stern von Kleene
• Regelmäßiger Ausdruck