Álgebra de Kleene

Compartir Imprimir Citar

En matemáticas, un álgebra de Kleene (KLAY-nee; llamado así por Stephen Cole Kleene) es un semicírculo idempotente (y por lo tanto parcialmente ordenado) dotado de un operador de cierre. Generaliza las operaciones conocidas a partir de expresiones regulares.

Definición

En la literatura se han dado varias definiciones no equivalentes de álgebras de Kleene y estructuras relacionadas. Aquí daremos la definición que parece ser la más común hoy en día.

Un álgebra de Kleene es un conjunto A junto con dos operaciones binarias +: A × A → A y ·: A × A → A y una función ^*: A → A, escrito como a + b, ab y a^* respectivamente, por lo que se cumplen los siguientes axiomas.

Asociación de + y ·: a +b + c) =a + b) + c y a()bc) =ab)c para todos a, b, c dentro A.
Computatividad de +: a + b = b + a para todos a, b dentro A
Distribución: a()b + c) =ab) + (ac) y (b + c)a =ba) + (ca) para todos a, b, c dentro A
Elementos de identidad para + y ·: Existe un elemento 0 en A tal que para todos a dentro A: a + 0 = 0 + a = a. Existe un elemento 1 en A tal que para todos a dentro A: a1 = 1a = a.
Aniquilación por 0: a0 = 0a = 0 para todos a dentro A.

Los axiomas anteriores definen un semianillo. Además requerimos:

+ es idempotente: a + a = a para todos a dentro A.

Ahora es posible definir una orden parcial ≤ en A configurando a ≤ b si y solo si a + b = b (o equivalentemente: a ≤ b si y solo si existe un x en A tales que a + x = b; con cualquier definición, a ≤ b ≤ a implica a = b). Con este orden podemos formular los últimos cuatro axiomas sobre la operación ^*:

1 + a()a^*≤ a^* para todos a dentro A.
1 +a^*)a ≤ a^* para todos a dentro A.
si a y x están dentro A tales que ax ≤ x, entonces a^*x ≤ x
si a y x están dentro A tales que xa ≤ x, entonces x()a^*≤ x

Intuitivamente, uno debería pensar en a + b como la "unión" o el "límite superior mínimo" de a y b y de ab como una multiplicación monótona, en el sentido de que a ≤ b implica ax ≤ bx. La idea detrás del operador estrella es a^* = 1 + a + aa + aaa +... Desde el punto de vista de la teoría del lenguaje de programación, también se puede interpretar + como "elección", · como "secuenciación" y ^* como "iteración".

Ejemplos

Corrección notarial entre
Álgebras y	+	·	^*	0	1
Expresiones periódicas	Silencio	no escrito	^*	∅	ε

Sea Σ un conjunto finito (un "alfabeto") y sea A el conjunto de todas las expresiones regulares sobre Σ. Consideramos dos expresiones regulares iguales si describen el mismo idioma. Entonces A forma un álgebra de Kleene. De hecho, esta es un álgebra de Kleene libre en el sentido de que cualquier ecuación entre expresiones regulares se deriva de los axiomas del álgebra de Kleene y, por lo tanto, es válida en cada álgebra de Kleene.

De nuevo, sea Σ un alfabeto. Sea A el conjunto de todos los lenguajes regulares sobre Σ (o el conjunto de todos los lenguajes libres de contexto sobre Σ; o el conjunto de todos los lenguajes recursivos sobre Σ; o el conjunto de todos lenguas sobre Σ). Entonces la unión (escrita como +) y la concatenación (escrita como ·) de dos elementos de A nuevamente pertenecen a A, y también la operación de estrella de Kleene aplicada a cualquier elemento de A. Obtenemos un álgebra de Kleene A siendo 0 el conjunto vacío y 1 el conjunto que solo contiene la cadena vacía.

Sea M un monoide con elemento de identidad e y sea A el conjunto de todos los subconjuntos de M. Para dos de tales subconjuntos S y T, sea S + T la unión de S y T y establecer ST = {st: s en S y t en T}. S^* se define como el submonoide de M generado por S, que se puede describir como { e} ∪ S ∪ SS ∪ SSS ∪... Entonces A forma un álgebra de Kleene siendo 0 el conjunto vacío y 1 {e}. Se puede realizar una construcción análoga para cualquier categoría pequeña.

Los subespacios lineales de un álgebra unital sobre un campo forman un álgebra de Kleene. Dados los subespacios lineales V y W, defina V + W como la suma de los dos subespacios, y 0 ser el subespacio trivial {0}. Defina $V \cdot W = span {v \cdot w | v \in V, w \in W}$ , el tramo lineal del producto de vectores de V y W respectivamente. Defina $1 = span {I}$ , el span de la unidad del álgebra. El cierre de V es la suma directa de todas las potencias de V.

{displaystyle V^{*}=bigoplus _{i=0}^{infty }V^{i}}

Suponga que M es un conjunto y A es el conjunto de todas las relaciones binarias en M. Tomando + como la unión, · como la composición y ^* como la clausura transitiva reflexiva, obtenemos un álgebra de Kleene.

Cada álgebra booleana con operaciones $lor$ y $land$ se convierte en un álgebra Kleene si usamos $lor$ para +, $land$ para · y conjunto a^* = 1 para todos a.

Se puede usar un álgebra de Kleene bastante diferente para implementar el algoritmo de Floyd-Warshall, calculando la longitud del camino más corto para cada dos vértices de un gráfico dirigido ponderado, mediante el algoritmo de Kleene, calculando una expresión regular por cada dos estados de un autómata finito determinista. Usando la línea de números reales extendida, tome a + b como el mínimo de a y b y ab como la suma ordinaria de a y b (con la suma de +∞ y −∞ definida como +∞). a^* se define como el número real cero para a no negativo y −∞ para a negativo. Esta es un álgebra de Kleene con elemento cero +∞ y un elemento el número real cero. Un gráfico dirigido ponderado se puede considerar como un autómata finito determinista, con cada transición etiquetada por su peso. Para cualquiera de los dos nodos gráficos (estados de autómatas), las expresiones regulares calculadas a partir del algoritmo de Kleene evalúan, en este álgebra de Kleene en particular, la longitud de ruta más corta entre los nodos.

Propiedades

Cero es el elemento más pequeño: 0 ≤ a para todos los a en A.

La suma a + b es el límite superior mínimo de a y b: tenemos a ≤ a + b y b ≤ a + b y si x es un elemento de A con a ≤ x y b ≤ x, luego a + b ≤ x. Del mismo modo, a₁ +... + a_n es el menor superior límite de los elementos a₁,..., a_n.

La multiplicación y la suma son monótonas: si a ≤ b, entonces

a + x ≤ b + x,
ax ≤ bx, y
xa ≤ xb

para todo x en A.

En cuanto a la operación estrella, tenemos

0^* = 1 y 1^* = 1,
a ≤ b implicación a^* ≤ b^* (Monotonicity),
aⁿ ≤ a^* para cada número natural n, donde aⁿ se define como n- multiplicación múltiple a,
()a^*)a^*) a^*,
()a^*)^* = a^*,
1 + a()a^*) a^* = 1 +a^*)a,
ax = xb implicadoa^*)x = x()b^*),
()ab)^*)a = a()ba)^*),
()a+b)^* = a^*()b()a^*)^*, y
pq = 1 = qp implicación q()a^*)p =qap)^*.

Si A es un álgebra de Kleene y n es un número natural, entonces se puede considerar el conjunto M_n(A) que consta de todas las matrices n-by-n con entradas en A. Usando las nociones ordinarias de suma y multiplicación de matrices, se puede definir una operación ^* única de modo que M_n(A) se convierte en un álgebra de Kleene.

Historia

Kleene introdujo expresiones regulares y dio algunas de sus leyes algebraicas. Aunque no definió las álgebras de Kleene, solicitó un procedimiento de decisión para la equivalencia de expresiones regulares. Redko demostró que ningún conjunto finito de axiomas ecuacionales puede caracterizar el álgebra de los lenguajes regulares. Salomaa dio axiomatizaciones completas de esta álgebra, sin embargo, dependiendo de las reglas de inferencia problemáticas. El problema de proporcionar un conjunto completo de axiomas, que permitiría la derivación de todas las ecuaciones entre expresiones regulares, fue estudiado intensamente por John Horton Conway bajo el nombre de álgebras regulares, sin embargo, la mayor parte de su tratamiento fue infinito. En 1981, Kozen dio un sistema deductivo ecuacional infinitario completo para el álgebra de lenguajes regulares. En 1994, dio el sistema de axiomas finitos anterior, que usa igualdades incondicionales y condicionales (considerando a ≤ b como una abreviatura de a + b = b), y es ecuacionalmente completa para el álgebra de lenguajes regulares, es decir, dos expresiones regulares a y b denota el mismo idioma solo si a = b se sigue de los axiomas anteriores.

Generalización (o relación con otras estructuras)

Las álgebras de Kleene son un caso particular de semianillos cerrados, también llamados semianillos cuasi-regulares o semianillos de Lehmann, que son semianillos en los que cada elemento tiene al menos un cuasi-inverso que satisface la ecuación: a* = aa* + 1 = a*a + 1. Esta cuasi-inversa no es necesariamente única. En un álgebra de Kleene, a* es la solución mínima de las ecuaciones de punto fijo: X = aX + 1 y X = Xa + 1.

Los semicírculos cerrados y las álgebras de Kleene aparecen en los problemas de ruta algebraica, una generalización del problema de la ruta más corta.

Álgebra de Kleene

Definición

Ejemplos

Propiedades

Historia

Generalización (o relación con otras estructuras)

Notas y referencias

Teoría del nudo

Conjuntos separados

Co-NP