Algebra Kleene

Kleene algebra - i teoretisk datalogi , en særlig algebraisk struktur introduceret af den amerikanske matematiker Stephen Kleene , som er en generalisering af regulært udtryk algebra .

Definition

Kleene- algebraen kaldes signaturalgebraen , som er en (ikke-kommutativ) idempotent semiring (med enhed), det vil sige, opfylder aksiomerne : $\mathcal{K}$ $\langle 0,1,+,\cdot ,{}^{*}\rangle$

$a + (b + c) = (a + b) + c$ ( associativitet af tilføjelse),
$a + b = b + a$ ( kommutativitet af tilføjelse),
$a+0=a$ ,
$a+a=a$ ( tilsætnings idempotens ),
$a(bc)=(ab)c$ ( associativitet af multiplikation),
$a1=1a=a$ ,
$a0=0a=0$ ,
$a(b+c)=ab+ac$ , (venstre fordeling ),
$(a+b)c=ac+bc$ , (rigtig fordeling ),

for hvilke fire nye aksiomer også er gyldige:

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

hvor den delordre er givet af ækvivalensen . Operationen "*" kaldes en iteration eller en Kleene- stjerne . $\leqslant$ $a\leqslant b\Leftrightarrow a+b=b$

Implementeringer

Det fremgår tydeligt af definitionen, at Kleene-algebraen ikke er specificeret specifikt - det er enhver algebra, der opfylder de anførte aksiomer. Det vil sige, at definitionen faktisk definerer en bestemt klasse af algebraer. Standardeksemplet på en Kleene -algebra er det regulære udtryk algebra . Samtidig er elementerne sæt af strenge, med hensyn til et eller andet fast alfabet , 0 er et tomt sæt, 1 er et sæt bestående af et tomt tegn, addition fortolkes som en mængde-teoretisk forening, multiplikation er givet ved formel , hvor er strengsammenkædningsoperationen . En iteration er defineret som foreningen af alle sæt . $\mathcal{K}$ $\Sigma$ ${\displaystyle ab=\{cat(x,y)|x\in a,y\in b\))$ $kat$ $a^{*}$ ${\displaystyle a^{i}=\underbrace {a\cdot \ldots \cdot a} _{i))$

Ud over standardfortolkningen er der mange andre.

Litteratur

Dexter Kozen Om Kleene algebraer og lukkede semiringer. — I Rovan, redaktør, Proc. Matematik. Fundet. Comput. Sci., bind 452 af Lecture Notes in Computer Science, side 26-47. Springer , 1990. Online: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps