algebry Kleene'a

W matematyce algebra Kleene'a ( / k l eɪ n i . / KLAY -nee ; nazwana na cześć Stephena Cole'a Kleene'a ) jest idempotentnym (a więc częściowo uporządkowanym) semiringiem wyposażonym w operator domknięcia Uogólnia operacje znane z wyrażeń regularnych .

Definicja

W literaturze podano różne nierównoważne definicje algebr Kleene'a i powiązanych struktur. Tutaj podamy definicję, która wydaje się być obecnie najbardziej powszechna.

Algebra Kleene'a jest zbiorem A wraz z dwiema operacjami binarnymi + : A × A → A i · : A × A → A i jedną funkcją ^* : A → A , zapisaną odpowiednio jako a + b , ab i a ^* , tak że spełnione są następujące aksjomaty.

Łączność + i ·: a + ( b + c ) = ( a + b ) + c i a ( bc ) = ( ab ) c dla wszystkich a , b , c w A .
Przemienność +: a + b = b + a dla wszystkich a , b w A
Dystrybucja : a ( b + c ) = ( ab ) + ( ac ) and ( b + c ) a = ( ba ) + ( ca ) dla wszystkich a , b , c w A
Elementy tożsamości dla + i ·: Istnieje element 0 w A taki, że dla wszystkich a w A : a + 0 = 0 + a = a . Istnieje element 1 w A taki, że dla wszystkich a w A : a 1 = 1 a = a .
Unicestwienie przez 0: a 0 = 0 a = 0 dla wszystkich a w A .

Powyższe aksjomaty definiują semiring . Wymagamy ponadto:

+ jest idempotentny : a + a = a dla wszystkich a w A .

Możliwe jest teraz zdefiniowanie porządku częściowego ≤ na A poprzez ustawienie a ≤ b wtedy i tylko wtedy, gdy a + b = b (lub równoważnie: a ≤ b wtedy i tylko wtedy, gdy istnieje x w A takie, że a + x = b ; z dowolną definicją a ≤ b ≤ a implikuje a = b ). W tym porządku możemy sformułować cztery ostatnie aksjomaty dotyczące operacji ^* :

1 + za ( za ^* ) ≤ za ^* dla wszystkich za w ZA .
1 + ( za ^* ) za ≤ za ^* dla wszystkich za w ZA .
jeśli a i x są w A takie, że ax ≤ x , to a ^* x ≤ x
jeśli a i x są w A takie, że xa ≤ x , to x ( a ^* ) ≤ x

Intuicyjnie, należy myśleć o a + b jako o „sumie” lub „najmniejszej górnej granicy” a i b , a ab jako o mnożeniu, które jest monotoniczne w tym sensie, że a ≤ b implikuje ax ≤ bx . Ideą operatora gwiazdy jest a ^* = 1 + a + aa + aaa + ... Z punktu widzenia teorii języka programowania , można również interpretować + jako „wybór”, · jako „sekwencjonowanie”, a ^* jako „iterację”.

Przykłady

Notacyjna korespondencja między
Algebry Kleene'a i	+	·	^*	0	1
Wyrażenia regularne	\|	nie napisane	^*	∅	ε

Niech Σ będzie skończonym zbiorem („alfabetem”) i niech A będzie zbiorem wszystkich wyrażeń regularnych nad Σ. Uważamy, że dwa takie wyrażenia regularne są równe, jeśli opisują ten sam język . Wtedy A tworzy algebrę Kleene'a. W rzeczywistości jest to swobodna algebra Kleene'a w tym sensie, że każde równanie między wyrażeniami regularnymi wynika z aksjomatów algebry Kleene'a i dlatego jest ważne w każdej algebrze Kleene'a.

Ponownie niech Σ będzie alfabetem. Niech A będzie zbiorem wszystkich języków regularnych nad Σ (lub zbiorem wszystkich języków bezkontekstowych nad Σ; lub zbiorem wszystkich języków rekurencyjnych nad Σ; lub zbiorem wszystkich języków nad Σ). Wtedy suma (zapisana jako +) i konkatenacja (zapisana jako ·) dwóch elementów A ponownie należy do A , podobnie jak operacja gwiazdy Kleene'a zastosowana do dowolnego elementu A . Otrzymujemy algebrę Kleene A gdzie 0 jest pustym zbiorem , a 1 jest zbiorem zawierającym tylko pusty łańcuch .

Niech M będzie monoidem z elementem identycznym e i niech A będzie zbiorem wszystkich podzbiorów M . Dla dwóch takich podzbiorów S i T niech S + T będzie sumą S i T i ustawmy ST = { st : s w S i t w T }. S ^* jest zdefiniowany jako podmonoid M generowany przez S , który można opisać jako { e } ∪ S ∪ SS ∪ SSS ∪ ... Wtedy A tworzy algebrę Kleene'a, w której 0 jest zbiorem pustym, a 1 jest { e }. Analogiczną konstrukcję można przeprowadzić dla dowolnej małej kategorii .

Podprzestrzenie liniowe algebry jednostkowej nad ciałem tworzą algebrę Kleene'a. Biorąc pod uwagę liniowe podprzestrzenie V i W zdefiniuj, że V + W będzie sumą dwóch podprzestrzeni, a 0 będzie trywialną podprzestrzenią {0}. Zdefiniuj $V \cdot W = rozpiętość {v \cdot w | v \in V, w \in W}$ , rozpiętość liniowa iloczynu wektorów odpowiednio z V i W. Zdefiniuj $1 = rozpiętość {I}$ , rozpiętość jednostki algebry. Zamknięcie V jest bezpośrednią sumą wszystkich potęg V .

{\ Displaystyle V ^ {*} = \ bigoplus _ {i = 0} ^ {\ infty} V ^ {i}}

Załóżmy, że M jest zbiorem, a A jest zbiorem wszystkich relacji binarnych na M . Biorąc + za sumę, · za złożenie, a ^* za zwrotne domknięcie przechodnie , otrzymujemy algebrę Kleene'a.

Każda algebra Boole'a z operacjami $i$ zamienia się w algebrę Kleene'a, jeśli użyjemy dla +, $\$ $\ displaystyle$ $}$ dla · i ^* = 1 dla wszystkich a .

Zupełnie inną algebrę Kleene'a można zastosować do implementacji algorytmu Floyda-Warshalla , obliczania długości najkrótszej ścieżki dla każdych dwóch wierzchołków ważonego grafu skierowanego za pomocą algorytmu Kleene'a , obliczania wyrażenia regularnego dla każdych dwóch stanów deterministycznego automatu skończonego . Korzystając z rozszerzonej osi liczb rzeczywistych , przyjmij, że a + b to minimum aib , a ab to zwykła suma a i b (przy czym suma +∞ i −∞ jest zdefiniowana jako +∞). a ^* jest zdefiniowane jako liczba rzeczywista zero dla nieujemnej a i −∞ dla ujemnej a . To jest algebra Kleene'a z elementem zerowym +∞ i jednym elementem liczbą rzeczywistą zero. Ważony graf skierowany można zatem uznać za deterministyczny automat skończony, w którym każde przejście jest oznaczone jego wagą. Dla dowolnych dwóch węzłów grafu (stanów automatów) wyrażenia regularne obliczone z algorytmu Kleene'a oceniają w tej konkretnej algebrze Kleene'a najkrótszą długość ścieżki między węzłami.

Nieruchomości

Zero jest najmniejszym elementem: 0 ≤ a dla wszystkich a w A .

Suma a + b jest najmniejszą górną granicą a i b : mamy a ≤ a + b i b ≤ a + b i jeśli x jest elementem A z a ≤ x i b ≤ x , to a + b ≤ x . Podobnie 1 ₊ ... + a _n jest najmniejszą górną granicą elementów a ₁ , ... _, an .

Mnożenie i dodawanie są monotoniczne: jeśli a ≤ b , to

za + x ≤ b + x ,
topór ≤ bx , oraz
xa ≤ xb

dla wszystkich x w A .

Jeśli chodzi o działanie gwiazdy, mamy

0^* = 1 i 1 ^* = 1,
a ≤ b implikuje a ^* ≤ b ^* (monotoniczność),
a ⁿ ≤ a ^* dla każdej liczby naturalnej n , gdzie a ⁿ jest zdefiniowane jako n -krotne pomnożenie a ,
( za ^* )( za ^* ) = za ^* ,
( za ^* ) ^* = za ^* ,
1 + za ( za ^* ) = za ^* = 1 + ( za ^* ) za ,
ax = xb implikuje ( a ^* ) x = x ( b ^* ),
(( ab ) ^* ) za = za (( ba ) ^* ),
( za + b ) ^* = za ^* ( b ( za ^* )) ^* , i
pq = 1 = qp implikuje q ( za ^* ) p = ( qap ) ^* .

Jeśli A jest algebrą Kleene'a, a n jest liczbą naturalną, to można rozważyć zbiór M _n ( A ) składający się ze wszystkich n -by- n macierzy z wpisami w A . Używając zwykłych pojęć dodawania i mnożenia macierzy, można zdefiniować jednoznaczną ^* operację, dzięki której M _n ( A ) staje się algebrą Kleene'a.

Historia

Kleene wprowadził wyrażenia regularne i podał niektóre z ich praw algebraicznych. Chociaż nie zdefiniował algebr Kleene'a, poprosił o procedurę rozstrzygania równoważności wyrażeń regularnych. Redko udowodnił, że żaden skończony zbiór równań nie może scharakteryzować algebry języków regularnych. Salomaa podał kompletne aksjomatyzacje tej algebry, jednak w oparciu o problematyczne reguły wnioskowania. Problem dostarczenia pełnego zestawu aksjomatów, który pozwoliłby wyprowadzić wszystkie równania pomiędzy wyrażeniami regularnymi, był intensywnie badany przez Johna Hortona Conwaya pod nazwą algebr regularnych jednak większość jego leczenia była nieskończona. W 1981 roku Kozen przedstawił kompletny system dedukcji równań nieskończoności dla algebry języków regularnych. W 1994 roku podał powyższy skończony system aksjomatów, który wykorzystuje równości bezwarunkowe i warunkowe (biorąc pod uwagę a ≤ b jako skrót dla a + b = b ) i jest równaniowo kompletny dla algebry języków regularnych, czyli dwóch wyrażeń regularnych aib oznaczają ten sam język tylko wtedy, gdy a = b wynika z powyższych aksjomatów.

Uogólnienie (lub stosunek do innych struktur)

Algebry Kleene'a to szczególny przypadek zamkniętych półpierścieni , zwanych także półpierścieniami quasi-regularnymi lub półpierścieniami Lehmanna , które są półpierścieniami, w których każdy element ma co najmniej jedną quasi-odwrotność spełniającą równanie: a * = aa * + 1 = a * a + 1. Ta quasi-odwrotność niekoniecznie jest wyjątkowa. W algebrze Kleene a * jest najmniejszym rozwiązaniem równań punktu stałego : X = aX + 1 i X = Xa + 1.

Zamknięte półpierścienie i algebry Kleene pojawiają się w problemach ze ścieżkami algebraicznymi , uogólnieniem problemu najkrótszej ścieżki .

Zobacz też

Uwagi i odniesienia

Kozen, Dexter . „CS786 Wiosna 04, Wprowadzenie do algebry Kleene” .

Dalsza lektura

Petera Höfnera (2009). Rachunki algebraiczne dla systemów hybrydowych . BOD – Książki na żądanie. s. 10–13. ISBN 978-3-8391-2510-6 . Wprowadzenie do tej książki stanowi przegląd postępów w dziedzinie algebry Kleene dokonanych w ciągu ostatnich 20 lat, które nie zostały omówione w powyższym artykule.