En matemáticas , un álgebra de Kleene ( / ˈk l eɪ n i / KLAY -nee ; llamado así por Stephen Cole Kleene ) es un semiring idempotente (y por lo tanto parcialmente ordenado) dotado de un operador de cierre . [1] Generaliza las operaciones conocidas de expresiones regulares .
En la literatura se han dado varias definiciones no equivalentes de álgebras de Kleene y estructuras relacionadas. [2] 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 , escritas como a + b , ab y a * respectivamente, de modo que se satisfacen los siguientes axiomas.
Los axiomas anteriores definen un semiring . Requerimos además:
Ahora es posible definir un orden parcial ≤ en A estableciendo a ≤ b si y sólo si a + b = b (o equivalentemente: a ≤ b si y sólo si existe una x en A tal 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 * :
Intuitivamente, uno debería pensar en a + b como la "unión" o el "límite superior mínimo" de a y b y en ab como una multiplicación que es 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". .
Sea Σ un conjunto finito (un "alfabeto") y sea A el conjunto de todas las expresiones regulares sobre Σ. Consideramos que dos de estas expresiones regulares son iguales si describen el mismo lenguaje . Entonces A forma un álgebra de Kleene. De hecho, ésta 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 todas las álgebras 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 los lenguajes sobre Σ). Entonces la unión (escrita como +) y la concatenación (escrita como ·) de dos elementos de A pertenecen nuevamente a A , al igual que la operación estrella de Kleene aplicada a cualquier elemento de A. Obtenemos un álgebra A de Kleene siendo 0 el conjunto vacío y 1 el conjunto que sólo 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 estos subconjuntos S y T , sea S + T la unión de S y T y establezca ST = { st : s en S y t en T }. S * se define como el submonoide de M generado por S , que puede describirse como { e } ∪ S ∪ SS ∪ SSS ∪... Entonces A forma un álgebra de Kleene donde 0 es el conjunto vacío y 1 es { 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 como el subespacio trivial {0}. Definir V · W = intervalo {v · w | v ∈ V, w ∈ W} , el tramo lineal del producto de vectores de V y W respectivamente. Defina 1 = span {I} , el span de la unidad del álgebra. La clausura de V es la suma directa de todas las potencias de V.
Supongamos 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 de Boole con operaciones se convierte en un álgebra de Kleene si usamos for +, for · y establecemos a * = 1 para todo a .
Se puede utilizar 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 para cada dos estados de un autómata finito determinista . Usando la recta numérica real 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 puede considerarse entonces como un autómata finito determinista, con cada transición etiquetada por su peso. Para dos nodos de gráfico cualesquiera (estados de autómata), las expresiones regulares calculadas a partir del algoritmo de Kleene evalúan, en este álgebra de Kleene en particular, la longitud del camino más corto entre los nodos. [4]
Cero es el elemento más pequeño: 0 ≤ a para todo 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 , entonces a + b ≤ X . De manera similar, a 1 + ... + a n es el límite superior mínimo de los elementos a 1 , ..., a n .
La multiplicación y la suma son monótonas: si a ≤ b , entonces
para todo x en A .
Respecto a la operación estrella, tenemos
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 por n con entradas en A. Utilizando las nociones ordinarias de suma y multiplicación de matrices, se puede definir una operación * única de modo que M n ( A ) se convierta en un álgebra de Kleene.
Kleene introdujo las expresiones regulares y dio algunas de sus leyes algebraicas. [6] [7] Aunque no definió las álgebras de Kleene, pidió un procedimiento de decisión para la equivalencia de expresiones regulares. [8] Redko demostró que ningún conjunto finito de axiomas ecuacionales puede caracterizar el álgebra de los lenguajes regulares. [9] Salomaa dio axiomatizaciones completas de esta álgebra, aunque dependiendo de reglas de inferencia problemáticas. [10] El problema de proporcionar un conjunto completo de axiomas, que permitiría derivar todas las ecuaciones entre expresiones regulares, fue estudiado intensamente por John Horton Conway bajo el nombre de álgebras regulares , [11] sin embargo, la mayor parte de su tratamiento fue infinitario. . En 1981, Kozen proporcionó un sistema deductivo ecuacional infinito completo para el álgebra de lenguajes regulares. [12] En 1994, dio el sistema de axioma finito anterior, que utiliza igualdades incondicionales y condicionales (considerando a ≤ b como una abreviatura de a + b = b ), y es ecuacionalmente completo para el álgebra de lenguajes regulares, es decir, dos expresiones regulares a y b denotan el mismo lenguaje sólo si a = b se sigue de los axiomas anteriores. [13]
Las álgebras de Kleene son un caso particular de semirings cerrados , también llamados semirings cuasi-regulares o semirings de Lehmann , que son semirings 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. [14] [15] 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. [15]
Los semianillos cerrados y las álgebras de Kleene aparecen en los problemas de camino algebraico , una generalización del problema del camino más corto . [15]
