En matemáticas , un álgebra de Kleene ( / ˈk l eɪ n i / KLAY -nee ; llamada así por Stephen Cole Kleene ) es un semianillo idempotente ( y por lo tanto parcialmente ordenado) dotado de un operador de cierre . [1] Generaliza las operaciones conocidas a partir de expresiones regulares .
En la literatura se han dado varias definiciones desiguales de álgebras de Kleene y estructuras relacionadas. [2] Aquí daremos la definición que parece ser la más común en la actualidad.
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 semianillo . Además, necesitamos:
Ahora es posible definir un orden parcial ≤ en A haciendo 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 , uno también 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 expresiones regulares de este tipo son iguales si describen el mismo lenguaje . Entonces A forma un álgebra de Kleene. De hecho, se trata de un álgebra de Kleene libre en el sentido de que cualquier ecuación entre expresiones regulares se deduce de los axiomas del álgebra de Kleene y, por lo tanto, es válida en cualquier álgebra de Kleene.
Sea Σ nuevamente un alfabeto. Sea A el conjunto de todos los idiomas regulares sobre Σ (o el conjunto de todos los idiomas libres de contexto sobre Σ; o el conjunto de todos los idiomas recursivos sobre Σ; o el conjunto de todos los idiomas sobre Σ). Entonces la unión (escrita como +) y la concatenación (escrita como ·) de dos elementos de A pertenecen nuevamente a A , y lo mismo ocurre con la operación de estrella de Kleene aplicada a cualquier elemento de A . Obtenemos un álgebra de Kleene A con 0 siendo el conjunto vacío y 1 siendo el conjunto que solo contiene la cadena vacía .
Sea M un monoide con elemento 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 el conjunto 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 con 0 siendo el conjunto vacío y 1 siendo { e }. Se puede realizar una construcción análoga para cualquier categoría pequeña .
Los subespacios lineales de un álgebra unitaria sobre un cuerpo 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}. Defina V · W = span {v · w | v ∈ V, w ∈ W} , el span lineal del producto de los 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 el cierre transitivo reflexivo , obtenemos un álgebra de Kleene.
Toda álgebra de Boole con operaciones y se convierte en un álgebra de Kleene si usamos para +, para · 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 grafo dirigido ponderado , mediante el algoritmo de Kleene , calculando una expresión regular para cada dos estados de un autómata finito determinista . Utilizando 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 cero elementos +∞ y un elemento el número real cero. Un grafo dirigido ponderado puede entonces considerarse como un autómata finito determinista, con cada transición etiquetada por su peso. Para cualesquiera dos nodos de gráfico (estados de autómata), las expresiones regulares calculadas a partir del algoritmo de Kleene evalúan, en esta álgebra de Kleene particular, la longitud de ruta más corta entre los nodos. [4]
El 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 consiste en 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 para 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, sin embargo dependiendo de reglas de inferencia problemáticas. [10] El problema de proporcionar un conjunto completo de axiomas, que permitiera la derivación de todas las ecuaciones entre expresiones regulares, fue estudiado intensivamente por John Horton Conway bajo el nombre de álgebras regulares , [11] sin embargo, la mayor parte de su tratamiento fue infinitario. En 1981, Kozen dio un sistema deductivo ecuacional infinitario completo para el álgebra de los lenguajes regulares. [12] En 1994, dio el sistema de axiomas finitos 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 solo si a = b se sigue de los axiomas anteriores. [13]
Las álgebras de Kleene son un caso particular de semianillos cerrados , también llamados semianillos cuasirregulares 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. Este cuasi-inverso no es necesariamente único. [14] [15] En un álgebra de Kleene, a * es la solución mínima para las ecuaciones de punto fijo : X = aX + 1 y X = Xa + 1. [15]
Los semianillos cerrados y las álgebras de Kleene aparecen en problemas de trayectorias algebraicas , una generalización del problema de la trayectoria más corta . [15]
