Клинијева алгебра

У математици, Клинијева алгебра (названа по Стефану Колу Клинију) је једна од следеће две ствари:

Гранична дистрибутивна мрежа са инволуцијом која задовољава Де Морганове законе, и неједнакост x ˄ -x ≤ y ˅ -y. Према томе, свака Булова алгебра је и Клинијева алгебра, али већина Клинијевих алгебри нису Булове алгебре. Баш као што су Булове алгбре повезане са класичним пропозиционим логиком, Клинијеве алгебре су повезане са Клинијевом тро-вредносном логиком.
Алгебарска структура која генерише операције познате из регуларних израза. Преостали део овог чланка слаже се са идејом Клинијеве алгебре.

Дефиниција уреди

У литератури се јављају различите нееквивалентне дефиниције Клинијеве алгебре и структуре повезане са тим. Погледати Козен за преглед. Овде ћемо дати дефиницију која се данас најчешће користи.

Клинијева алгебра је скуп А са две бинарне операције +: А × А → А и •: А × А → А и једном функцијом *: А → А које редом пишемо као а+б, аб и а* тако да следеће аксиоме буду задовољене.

Асоцијативност у односу на + и •: а + (b + c) = (а + b) + c и а(bc) =(аb)c за свако a, b, c из А
Комутативност у односу на сабирање: 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 ако и само ако a + b = b (или еквивалентно: a ≤ b ако и само ако постоји такво x у А такво да је a + x = b). Уз помоћ овог уређења моземо да формулишемо две преостале аксиоме везане за операцију *:

1 + а(а*) ≤ а* за свако а из А
1 + (а*)а ≤ а* за свако а из А
Ако су а и x из А такви да је ax ≤ x тада a*x ≤ x
Ако су а и x из А такви да је xa ≤ x, тада је x(a*) ≤ x

Интуитивно, неко би a + b схватио као “унију“ или “најмању горњу границу“ од а и b и од аб као множење које је монотоно, у смислу да а ≤ b имплицира ax ≤ bx. Идеја скривена иза операције * је а* = 1 + а + аа + ааа + ... Са тачке гледиста прагматске теорије језика, неко би такође + могао интерпретирати као “одабир“ или “секвенцирање“, и * као “понављање“.

Примери уреди

Нека је ∑ конацан скуп (“алфабет“) и нека је А скуп регуларних израза над ∑. Сматрамо да су два регуларна израза једнака ако описују исти језик. Тада А чини Клинијеву алгебру. Ово је слободна клинијева алгебра у смислу да свака једнакост међу регуларним изразима произилази из аксиома Клинијеве алгебре, па смим тим важи у свакој Клинијевој алгебри.

Нека је поново ∑ алфабет. Нека је А скуп регуларних језика над ∑ (или скуп контекстно-слободних језика над ∑; или скуп рекурзивних језика над ∑; или скуп свих језика над ∑). Тада унија (записана као +) и конкатенација (записана као •) два елемента из А поново припада А, а такође и операција Клинијеве звездице примењене на било који елемент из А. Клинијеву алгебру А означену са 0 користимо као празан скуп, а са 1 као скуп који садржи само празан стринг.

Нека је M моноид са неутралним елементом е и нека је А скуп свих подскупова од M. За два таква подскупа S и Т, нека је S + Т унија S и Т и ознацимо ST = {st: s из S и t из Т}. S* је дефинисано као подмоноид од M генерисан са S, што се може описати као {е}∪S ∪ СС ∪ССС∪… Тада А представља Клинијеву алгебру где је 0 празан скуп и 1 је {е}. Аналогна конструкција се мозе применити за било коју малу категорију.

Претпоставимо да је M скуп и да је А скуп свих бинарних операција над M. Узимајуци да је + унија, • композиција и * рефлексивно транзитивна, добијамо Клинијеву алгебру.

Свака Булова алгебра са операцијама и постаје Клинијева алгебра ако користимо за + , за • , и ознацимо да је а* = 1 за свако а.

Веома различита Клинијева алгебра се користи када рачунамо најкраце стазе у тежинским усмереним графовима: нека је А продузена реална оса, узмемо да је а + b минимум од а и b и ab обична сума од а и b (где суму од +∞ и -∞ дефинишемо као +∞). а* је дефинисано као реална нула за ненегативно а и -∞ за негативно а. Ово је Клинијева алгебра са нултим елементом +∞ и једном реалном нулом.

Особине уреди

Нула је најмањи елемент: 0 ≤ а за свако а из А.

Сума а + b је најмања горња граница од а и b: имамо да је а ≤ а + b и b ≤ a + b и ако је x елемент из А тако да је а ≤ x и b ≤ x тада је а + b ≤ x. Слицно a1 +...+ an је најмања горња граница елемената a1, ..., an.

Множење и сабирање су монотони: ако је a ≤ b, тада је a + x ≤ b + x, ax ≤ bx и xa ≤ xb за свако x из А.

Што се тиче операције *, имамо да је 0* = 1 и 1* = 1, што је монотоно (а ≤ b имплицира а* ≤ b*), и тада је an ≤ а* за сваки пиродан број n. Осим тога, (а*)(а*) = а*, (а*)* = а*, и a ≤ b* важи ако и само ако је a* ≤ b*.

Ако је А Клинијева алгебра и н природан број тада се скуп Mn(A) састоји из свих n пута n матрица над скупом А. Користећи обично сабирање и множење матрица моземо дефинисати јединствену *-операцију тако да Mn(A) постане Клинијева алгебра.

Историја уреди

Клинијеве алгебре није дефинисао Клини; увео је регуларне изразе и захтевао комлетан скуп аксиома што би омогуцило добијање свих једнацина међу регуларним изразима. Овај проблем је прво изучавао Џон Хортон Конвеј под именом регуларне алгебре. Аксиоме Клинијевих алгебри су решиле овај проблем што је прво показао Декстер Козен.

Литература уреди

1. Декстер Козен: On Kleene algebras and closed semirings. У Рован-у, едитор, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, странице 26-47. Спрингер, 1990. На интернету: 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. Поглавље IV.