Algebra Kleene

Kleene algebra - în informatica teoretică , o structură algebrică specială introdusă de matematicianul american Stephen Kleene , care este o generalizare a algebrei cu expresii regulate .

Definiție

Algebra Kleene se numește algebra semnăturii , care este un semiring idempotent (necomutativ) (cu unitate), adică satisface axiomele : $\mathcal{K}$ $\langle 0,1,+,\cdot ,{}^{*}\rangle$

$a + (b + c) = (a + b) + c$ ( asociativitatea adunării),
$a + b = b + a$ ( comutativitatea adunării),
$a+0=a$ ,
$a+a=a$ ( idempotenta adaosului),
$a(bc)=(ab)c$ ( asociativitatea înmulțirii),
$a1=1a=a$ ,
$a0=0a=0$ ,
$a(b+c)=ab+ac$ , ( distributivitatea stângă ),
$(a+b)c=ac+bc$ , ( distributivitatea dreaptă ),

pentru care sunt valabile și patru noi axiome:

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

unde ordinea parțială este dată de echivalența . Operația „*” se numește o iterație sau o stea Kleene . $\leqslant$ $a\leqslant b\Leftrightarrow a+b=b$

Implementări

Este clar din definiție că algebra Kleene nu este specificată în mod specific - este orice algebră care satisface axiomele enumerate. Adică, de fapt, definiția definește o anumită clasă de algebre. Exemplul standard de algebră Kleene este expresia regulată algebră . În același timp, elementele sunt mulțimi de șiruri, în raport cu un alfabet fix , 0 este o mulțime goală, 1 este o mulțime formată dintr-un caracter gol, adunarea este interpretată ca o uniune teoretică a mulțimii, înmulțirea este dată de formula , unde este operația de concatenare a șirurilor . O iterație este definită ca uniunea tuturor mulțimilor . $\mathcal{K}$ $\Sigma$ $ab=\{cat(x,y)|x\in a,y\in b\)$ $pisică$ $a^{*}$ $a^{i}=\underbrace {a\cdot \ldots \cdot a} _{i)$

Pe lângă interpretarea standard, există multe altele.

Literatură

Dexter Kozen Despre algebrele Kleene și semiinele închise. — În Rovan, redactor, Proc. Matematică. Găsite. Calculator. Sci., volumul 452 din Lecture Notes in Computer Science, paginile 26-47. Springer , 1990. Online: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps