Klinijeva algebra

U matematici, Klinijeva algebra (nazvana po Stefanu Kolu Kliniju) je jedna od sledeće dve stvari:

• Granična distributivna mreža sa involucijom koja zadovoljava De Morganove zakone, i nejednakost x ˄ -x ≤ y ˅ -y. Prema tome, svaka Bulova algebra je i Klinijeva algebra, ali većina Klinijevih algebri nisu Bulove algebre. Baš kao što su Bulove algbre povezane sa klasičnim propozicionim logikom, Klinijeve algebre su povezane sa Klinijevom tro-vrednosnom logikom.
• Algebarska struktura koja generiše operacije poznate iz regularnih izraza. Preostali deo ovog članka slaže se sa idejom Klinijeve algebre.

Definicija

U literaturi se javljaju različite neekvivalentne definicije Klinijeve algebre i strukture povezane sa tim. Pogledati Kozen za pregled. Ovde ćemo dati definiciju koja se danas najčešće koristi.

Klinijeva algebra je skup A sa dve binarne operacije +: A × A → A i •: A × A → A i jednom funkcijom *: A → A koje redom pišemo kao a+b, ab i a* tako da sledeće aksiome budu zadovoljene.

• Asocijativnost u odnosu na + i •: a + (b + c) = (a + b) + c i a(bc) =(ab)c za svako a, b, c iz A
• Komutativnost u odnosu na sabiranje: a + b = b + a]- za svako a i b iz A
• Distributivnost: a(b + c) = (ab) + (ac) i (b + c)a = (ba) + (ca) za svako a, b, c iz A
• Neutralni element za + i •: Postoji element 0 iz A takav da svako a iz A važi: a + 0 = 0 + a = a. Postoji element 1 iz A takav da za svako a iz A važi: a1 = 1a = a
• a0 = 0a = 0 za svako a iz A.

Gornje aksiome definišu poluprsten. Nadalje zahtevamo:

• + je idempotentna: a + a = a za svako a iz A

Sada je moguće definisati parcijalnu uređenost ≤ u skupu A stavljajući da je a ≤ -[b ako i samo ako a + b = b (ili ekvivalentno: a ≤ b ako i samo ako postoji takvo x u A takvo da je a + x = b). Uz pomoć ovog uređenja mozemo da formulišemo dve preostale aksiome vezane za operaciju *:

• 1 + a(a*) ≤ a* za svako a iz A
• 1 + (a*)a ≤ a* za svako a iz A
• Ako su a i x iz A takvi da je ax ≤ x tada a*x ≤ x
• Ako su a i x iz A takvi da je xa ≤ x, tada je x(a*) ≤ x

Intuitivno, neko bi a + b shvatio kao “uniju“ ili “najmanju gornju granicu“ od a i b i od ab kao množenje koje je monotono, u smislu da a ≤ b implicira ax ≤ bx. Ideja skrivena iza operacije * je a* = 1 + a + aa + aaa + ... Sa tačke gledista pragmatske teorije jezika, neko bi takođe + mogao interpretirati kao “odabir“ ili “sekvenciranje“, i * kao “ponavljanje“.

Primeri

Neka je ∑ konacan skup (“alfabet“) i neka je A skup regularnih izraza nad ∑. Smatramo da su dva regularna izraza jednaka ako opisuju isti jezik. Tada A čini Klinijevu algebru. Ovo je slobodna klinijeva algebra u smislu da svaka jednakost među regularnim izrazima proizilazi iz aksioma Klinijeve algebre, pa smim tim važi u svakoj Klinijevoj algebri.

Neka je ponovo ∑ alfabet. Neka je A skup regularnih jezika nad ∑ (ili skup kontekstno-slobodnih jezika nad ∑; ili skup rekurzivnih jezika nad ∑; ili skup svih jezika nad ∑). Tada unija (zapisana kao +) i konkatenacija (zapisana kao •) dva elementa iz A ponovo pripada A, a takođe i operacija Klinijeve zvezdice primenjene na bilo koji element iz A. Klinijevu algebru A označenu sa 0 koristimo kao prazan skup, a sa 1 kao skup koji sadrži samo prazan string.

Neka je M monoid sa neutralnim elementom e i neka je A skup svih podskupova od M. Za dva takva podskupa S i T, neka je S + T unija S i T i oznacimo ST = {st: s iz S i t iz T}. S* je definisano kao podmonoid od M generisan sa S, što se može opisati kao {e}∪S ∪ SS ∪SSS∪… Tada A predstavlja Klinijevu algebru gde je 0 prazan skup i 1 je {e}. Analogna konstrukcija se moze primeniti za bilo koju malu kategoriju.

Pretpostavimo da je M skup i da je A skup svih binarnih operacija nad M. Uzimajuci da je + unija, • kompozicija i * refleksivno tranzitivna, dobijamo Klinijevu algebru.

Svaka Bulova algebra sa operacijama i postaje Klinijeva algebra ako koristimo za + , za • , i oznacimo da je a* = 1 za svako a.

Veoma različita Klinijeva algebra se koristi kada računamo najkrace staze u težinskim usmerenim grafovima: neka je A produzena realna osa, uzmemo da je a + b minimum od a i b i ab obična suma od a i b (gde sumu od +∞ i -∞ definišemo kao +∞). a* je definisano kao realna nula za nenegativno a i -∞ za negativno a. Ovo je Klinijeva algebra sa nultim elementom +∞ i jednom realnom nulom.

Osobine

Nula je najmanji element: 0 ≤ a za svako a iz A.

Suma a + b je najmanja gornja granica od a i b: imamo da je a ≤ a + b i b ≤ a + b i ako je x element iz A tako da je a ≤ x i b ≤ x tada je a + b ≤ x. Slicno a1 +...+ an je najmanja gornja granica elemenata a1, ..., an.

Množenje i sabiranje su monotoni: ako je a ≤ b, tada je a + x ≤ b + x, ax ≤ bx i xa ≤ xb za svako x iz A.

Što se tiče operacije *, imamo da je 0* = 1 i 1* = 1, što je monotono (a ≤ b implicira a* ≤ b*), i tada je an ≤ a* za svaki pirodan broj n. Osim toga, (a*)(a*) = a*, (a*)* = a*, i a ≤ b* važi ako i samo ako je a* ≤ b*.

Ako je A Klinijeva algebra i n prirodan broj tada se skup Mn(A) sastoji iz svih n puta n matrica nad skupom A. Koristeći obično sabiranje i množenje matrica mozemo definisati jedinstvenu *-operaciju tako da Mn(A) postane Klinijeva algebra.

Istorija

Klinijeve algebre nije definisao Klini; uveo je regularne izraze i zahtevao komletan skup aksioma što bi omogucilo dobijanje svih jednacina među regularnim izrazima. Ovaj problem je prvo izučavao Džon Horton Konvej pod imenom regularne algebre. Aksiome Klinijevih algebri su rešile ovaj problem što je prvo pokazao Dekster Kozen.

Literatura

1. Dekster Kozen: On Kleene algebras and closed semirings. U Rovan-u, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, stranice 26-47. Springer, 1990. Na internetu: http://www.cs.cornell.edu/~kozen/papers/kacs.ps.

2. J.H.Conway, Regular algebra and finite machines, Chapman and Hall. 1971. ISBN 978-0-412-10620-0. Poglavlje IV.

Vidi još

• Algebarske strukture
• Regularni izrazi