Álgebra Kleene

Álgebra de Kleene : en informática teórica , una estructura algebraica especial introducida por el matemático estadounidense Stephen Kleene , que es una generalización del álgebra de expresiones regulares .

Definición

El álgebra de Kleene se llama álgebra de firma , que es un semiring (con unidad) idempotente (no conmutativo), es decir, satisface los axiomas : $\mathcal{K}$ $\langle 0,1,+,\cdot,{}^{*}\rangle$

$a + (b + c) = (a + b) + c$ ( asociatividad de la suma),
$un + segundo = segundo + un$ ( conmutatividad de la suma),
${\ estilo de visualización a+0=a}$ ,
${\ estilo de visualización a + a = a}$ ( idempotencia de la suma),
${\ estilo de visualización a (bc) = (ab) c}$ ( asociatividad de la multiplicación),
${\ estilo de visualización a1 = 1a = a}$ ,
${\ estilo de visualización a0 = 0a = 0}$ ,
${\ estilo de visualización a (b + c) = ab + ac}$ , ( distributividad izquierda ),
${\ estilo de visualización (a + b) c = ac + bc}$ , ( distributividad derecha ),

para lo cual también son válidos cuatro nuevos axiomas:

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

donde el orden parcial viene dado por la equivalencia . La operación "*" se llama iteración o estrella de Kleene . $\leqslant$ $a\leqslant b\Leftrightarrow a+b=b$

Implementaciones

Está claro a partir de la definición que el álgebra de Kleene no se especifica específicamente; es cualquier álgebra que satisfaga los axiomas enumerados. Es decir, de hecho, la definición define una cierta clase de álgebras. El ejemplo estándar de un álgebra de Kleene es el álgebra de expresiones regulares . Al mismo tiempo, los elementos son conjuntos de cadenas, con respecto a algún alfabeto fijo , 0 es un conjunto vacío, 1 es un conjunto que consta de un carácter vacío, la suma se interpreta como una unión teórica de conjuntos, la multiplicación está dada por el fórmula , donde está la operación de concatenación de cadenas . Una iteración se define como la unión de todos los conjuntos . $\mathcal{K}$ $\Sigma$ ${\displaystyle ab=\{gato(x,y)|x\en a,y\en b\))$ ${\ estilo de pantalla gato}$ $un^{*}$ ${\displaystyle a^{i}=\underbrace {a\cdot \ldots \cdot a} _{i))$

Además de la interpretación estándar, hay muchas otras.

Literatura

Dexter Kozen Sobre álgebras de Kleene y semianillos cerrados. — En Rovan, editor, Proc. Matemáticas. Fundar. computar Sci., volumen 452 de Lecture Notes in Computer Science, páginas 26-47. Springer , 1990. En línea: https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps