Kleene algebra

I matematik svarer en Kleene-algebra (opkaldt efter den amerikanske logiker Stephen Cole Kleene ) til et af to begreber:

Et ordnet og distribuerende gitter med en involution, der opfylder De Morgans love og uligheden x ∧ - x ≤ y ∨ - y . Så hver boolsk algebra er en Kleene-algebra, hvor det gensidige er komplement. Ligesom boolske algebraer, der er baseret på klassiske logiske propositioner, er Kleene algebraer baseret på Kleene ternær logik .
En algebraisk struktur, der generaliserer kendte operationer ud fra regulære udtryk. Resten af denne artikel vil beskæftige sig med denne opfattelse af Kleene algebra. I starten af denne opfattelse finder vi matematikeren John Horton Conway, der introducerede den under navnet almindelige algebraer .

Definition

Mange ikke-ækvivalente definitioner af Kleene algebraer og relaterede strukturer er givet i litteraturen. Vi vil her give den definition, der synes mest almindeligt accepteret i dag.

En Kleene algebra er et sæt med to love indre præparat +: A × A → A og · : A × A → A , og operatør *: A → A . Disse love og denne operatør betegnes henholdsvis a + b , ab og a *. Disse operationer opfylder følgende aksiomer :

associativitet af + og ·: a + ( b + c ) = ( a + b ) + c og a ( bc ) = ( ab ) c for hver a , b , c af A .
kommutivitet af +: a + b = b + en for alle a , b i A .
distributivitet : a ( b + c ) = ( ab ) + ( ac ) og ( b + c ) er = ( BA ) + ( AC ) for alle a , b , c af A .
neutrale elementer for + og ·: der findes et element 0 af A således at for alle a af A : a + 0 = 0 + a = a . Der findes et element 1 af A sådan, at for alle a af A : a 1 = 1 a = a .
0 er et absorberende element : a 0 = 0 a = 0 for alle en i A .

Axiomerne ovenfor definerer en halvring . Vi tilføjer:

den idempotent af +: for alle a af A , en + en = a .

Det er derfor muligt at definere en forudbestilling ≤ på A ved at postulere a ≤ b, hvis og kun hvis a + b = b (eller ækvivalent, a ≤ b hvis og kun der findes c i A, således at a + c = b ). Denne ordrerelation gør det muligt at placere de sidste fire aksiomer på operatøren *:

1 + en ( en *) ≤ en * for alle en i A .
1 + ( en *) er ≤ en * for alle en i A .
hvis a og b er to elementer i A således, at ab ≤ b så a * b ≤ b .
hvis a og b er to elementer i A således, at ba ≤ b, så er b ( a *) ≤ b .

Intuitivt kan vi tænke på a + b som foreningen eller den mindste øvre grænse for a og b og af ab som en stigende multiplikation i den forstand, at a ≤ b indebærer økse ≤ bx . Ideen bag "stjerne" -operatoren er, at en * = 1 + a + aa + aaa + ... Fra synspunktet med programmeringsteorien kan vi fortolke + som en "valg" -operator ikke deterministisk, som "sekventiel" komposition "og * som" iteration ".

Eksempler

Lad Σ være et endeligt sæt (et "alfabet") og A sættet med regulære udtryk over Σ . To regulære udtryk er ens, hvis de beskriver det samme regulære sprog . Sættet A danner en Kleene-algebra. Faktisk er det endda en fri Kleene- algebra i den forstand, at enhver ligning, der er gyldig i denne algebra, er gyldig i enhver Kleene-algebra.

Lad Σ være et alfabet. Lad A være sættet med rationelle sprog på Σ (eller sæt af sprog uden sammenhæng på Σ eller endda sættet med alle rekursive sprog eller endelig sættet med alle sprog på Σ ). Den union (skriftlig +) og sammenkædning (skriftlig •) af to elementer i A tilhører A , og så driften af Kleene stjerne er en endomorfien af A . Vi får derefter en Kleene-algebra, hvor: og , undertiden bemærket , med hvilken betegner den tomme streng eller det tomme ord. $0 = \ tomme sæt$ $1 = \ {\ epsilon \}$ $\ Delta$ $\ epsilon$

Eller M en monoid med identitet som medlem e og enten A alle delmængder af M . Lad S og T være to undergrupper af M , lad S + T være foreningen af S og T og ST = {chain st | s i S og t i T }. S * defineres som submonoid af M genereret af S , intuitivt svarer det til { e } ∪ S ∪ SS ∪ SSS ∪ ... A danner derefter en Kleene-algebra med som 0, det tomme sæt og som 1, singleton { e }. Du kan lave en lignende konstruktion i en meget lille kategori .

Antag M et sæt og en alle binære relationer på M . Vi kan give M de tre operationer af Kleene algebras, nemlig unionen for +, sammensætningen for • og stjernen, refleksiv og transitiv lukning, for *. De to konstanter er for 0 den tomme relation (som ikke forbinder noget) og for 1 den fulde relation (som forbinder alt). Således udstyret ( M , +, •, *; 0, 1) er en Kleene algebra.

Enhver boolsk algebra udstyret med operationer og viser sig at være en Kleene-algebra, hvis vi identificerer med +, med •, at vi postulerer en * = 1 for alle a, og at 0 for Kleene-algebra er 0 for den boolske algebra og samme for 1. $\ vee$ $\ kile$ $\ vee$ $\ kile$

En bestemt Kleene-algebra er nyttig, når det kommer til beregning af de korteste stier i vægtede, rettede grafer : lad A være den færdige reelle linje , lad a + b være minimumet af a og b, og at ab er summen af den virkelige a og den virkelige b (summen af + ∞ og -∞ er pr. definition + ∞). a * er det reelle tal nul, hvis a er positivt eller nul og -∞, hvis a er strengt negativt. A er en Kleene-algebra, hvor 0 er værdien + ∞ og 1 er det reelle tal nul.

Ejendomme

Nul, betegnet 0, er det mindste medlem af sættet, det vil sige, 0 ≤ en for alle en i A .

Summen a + b er den mindste øvre grænse for en og b : vi har en ≤ en + b og b ≤ a + b , og hvis x er et element af A med en ≤ x og b ≤ x , derefter en + b ≤ x . Ligeledes er den mindste øvre grænse for elementerne . ${\ displaystyle a_ {1} + ... + a_ {n}}$ $a_ {1}, ..., a_ {n}$

Multiplikation og addition er monoton hvis en ≤ b , derefter en + x ≤ b + x , ax ≤ bx og xa ≤ xb for alle x af A .

I betragtning af operationen * har vi 0 * = 1 og 1 * = 1, dette * stiger ( a ≤ b betyder en * ≤ b *), og at en n ≤ a * for alle naturlige tal n . Desuden er ( a *) ( a *) = a *, ( a *) * = a * og a ≤ b * hvis og kun hvis a * ≤ b *.

Hvis A er en Kleene algebra og n et naturligt tal, kan betragtes som den indstillede M n ( A ) bestående af alle matricer n ved n med indgange i A . Ved anvendelse af de almindelige begreber matrix addition og multiplikation , kan vi definere en enkelt operation * således at M n ( A ) bliver en Kleene algebra.

Historie

Kleene algebraer blev ikke defineret af Kleene. Han introducerede regulære udtryk og postulerede eksistensen af et komplet sæt aksiomer, der ville udlede alle gyldige ligninger i regulære udtryk. De første aksiomer blev foreslået af John H. Conway og et system med komplette aksiomer, der definerede Kleene-algebraer og løsning af problemet, blev foreslået af Dexter Kozen , der demonstrerede deres fuldstændighed.

Se også

Noter og referencer

(fr) Denne artikel er helt eller delvist hentet fra den engelske Wikipedia- artikel med titlen " Kleene algebra " ( se listen over forfattere ) .

(i) JH Conway, Regelmæssig algebra og Finite Maskiner , Chapman og Hall, London, 1971.
For en oversigt kan vi se (i) Dexter Kozen , "We Kleene algebras and closed semirings" , i B. Rovan, Proc. Matematik. Fundet. Comput. Sci. , Springer, al. "Forelæsningsnotater inden for datalogi" ( nr . 452),1990( læs online ) , s. 26-47.