Algebra Kleene

Kleene algebra -- az elméleti számítástechnikában , Stephen Kleene amerikai matematikus által bevezetett speciális algebrai struktúra , amely a reguláris kifejezés algebra általánosítása .

Definíció

A Kleene- algebrát az aláírás algebrájának nevezzük , amely egy (nem kommutatív) idempotens félgyűrű (egységgel), azaz kielégíti az axiómákat : $\mathcal{K}$ $\langle 0,1,+,\cdot ,{}^{*}\rangle$

$a + (b + c) = (a + b) + c$ ( az összeadás asszociativitása ),
$a + b = b + a$ ( összeadás kommutativitása ),
$a+0=a$ ,
$a+a=a$ ( az összeadás idempotenciája ),
$a(bc)=(ab)c$ ( a szorzás asszociativitása ),
$a1=1a=a$ ,
$a0=0a=0$ ,
$a(b+c)=ab+ac$ , (bal oldali eloszlás ),
${\megjelenítési stílus (a+b)c=ac+bc}$ , (jobb eloszlás ),

amelyre négy új axióma is érvényes:

$1+aa^{*}\leqslant a^{*}$ ,
$1+a^{*}a\leqslant a^{*}$ ,
$(ab\leqslant b)\to (a^{*}b\leqslant b)$ ,
$(ab\leqslant a)\to (ab^{*}\leqslant a)$ ,

ahol a részleges sorrendet az ekvivalencia adja . A "*" műveletet iterációnak vagy Kleene - csillagnak nevezik . $\leqslant$ $a\leqslant b\Leftrightarrow a+b=b$

Megvalósítások

A definícióból kitűnik, hogy a Kleene-algebra nincs konkrétan megadva - ez bármely algebra kielégíti a felsorolt axiómákat. Vagyis a definíció az algebrák egy bizonyos osztályát határozza meg. A Kleene algebra standard példája a reguláris kifejezés algebra . Ugyanakkor az elemek karakterláncok halmazai, valamilyen rögzített ábécére tekintettel a 0 üres halmaz, az 1 egy üres karakterből álló halmaz, az összeadást halmazelméleti unióként értelmezzük, a szorzást a formula , ahol a karakterlánc összefűzési művelete . Az iteráció az összes halmaz uniója . $\mathcal{K}$ $\Sigma$ ${\displaystyle ab=\{cat(x,y)|x\in a,y\in b\))$ $cat$ $a^{*}$ ${\displaystyle a^{i}=\underbrace {a\cdot \ldots \cdot a} _{i))$

A standard értelmezésen kívül sok más is létezik.

Irodalom

Dexter Kozen Kleene algebrákról és zárt félgyűrűkről. – Rovanban, szerkesztő, Proc. Math. Megtalált. Comput. Sci., Lecture Notes in Computer Science, 452. kötet, 26-47. oldal. Springer , 1990. Online: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps