Álgebra de Kleene

En matemáticas y ciencias de la computación teórica , un álgebra de Kleene ( / ˈ k l eɪ n i / KLAY -nee ; llamada así por Stephen Cole Kleene ) es un semianillo que generaliza la teoría de las expresiones regulares : consiste en un conjunto que admite la unión (suma), la concatenación (multiplicación) y las operaciones de estrella de Kleene sujetas a ciertas leyes algebraicas. Se requiere que la suma sea idempotente (${\displaystyle x+x=x}$a pesar de${\displaystyle x}$), e induce un orden parcial definido por${\displaystyle x\leq y}$si${\displaystyle x+y=y}$. La operación de la estrella de Kleene, denominada${\displaystyle x^{*}}$, debe satisfacer las leyes de un operador de cierre . ^{[ 1 ]}

Las álgebras de Kleene tienen su origen en la teoría de expresiones regulares y lenguajes regulares introducida por Kleene en 1951 y estudiada por otros, incluidos VN Redko y John Horton Conway , quien introdujo el término en 1971. ^{[ 2 ]} El concepto fue popularizado más tarde por Dexter Kozen en la década de 1980, quien caracterizó completamente sus propiedades algebraicas y, en 1994, dio una axiomatización finita.

Las álgebras de Kleene tienen varias extensiones que se han estudiado, incluyendo las álgebras de Kleene con pruebas (KAT) introducidas por Kozen en 1997. ^{[ 3 ]} Las álgebras de Kleene y las álgebras de Kleene con pruebas tienen aplicaciones en la verificación formal de programas informáticos. ^{[ 4 ]} También se han aplicado para especificar y verificar redes informáticas . ^{[ 5 ]}

En la literatura se han dado varias definiciones no equivalentes de álgebras de Kleene y estructuras relacionadas. ^{[ 6 ]} Aquí daremos la definición que parece ser la más común en la actualidad.

Un álgebra de Kleene es una estructura${\displaystyle (A,+,\cdot ,^{*},0,1)}$, dónde${\displaystyle A}$es un conjunto que contiene${\displaystyle 0}$y${\displaystyle 1}$las operaciones${\displaystyle +}$y${\displaystyle \cdot }$son binarios y la operación${\displaystyle ^{*}}$es unario. El operador${\displaystyle \cdot }$a menudo se omite. Esta estructura satisface los siguientes axiomas.

• Asociatividad de${\displaystyle +}$y${\displaystyle \cdot }$:${\displaystyle (a+b)+c=a+(b+c)}$y${\displaystyle (ab)c=a(bc)}$a pesar de${\displaystyle a,b,c\in A}$.
• Conmutatividad de${\displaystyle +}$:${\displaystyle a+b=b+a}$a pesar de${\displaystyle a,b\in A}$.
• Distributividad :${\displaystyle a(b+c)=ab+ac}$y${\displaystyle (b+c)a=ba+ca}$a pesar de${\displaystyle a,b,c\in A}$.
• Elementos de identidad para${\displaystyle +}$y${\displaystyle \cdot }$: para todos${\displaystyle a\in A}$tenemos${\displaystyle a+0=0+a=a}$y${\displaystyle a1=1a=a}$.
• Aniquilación por${\displaystyle 0}$:${\displaystyle a0=0a=0}$a pesar de${\displaystyle a\in A}$.

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

• Idempotencia de${\displaystyle +}$:${\displaystyle a+a=a}$a pesar de${\displaystyle a\in A}$.

Ahora es posible definir un orden parcial ≤ en A estableciendo a ≤ b si y solo si a + b = b (o equivalentemente: a ≤ b si y solo si existe un 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 ^* :

• 1 + a ( a ^* ) ≤ a ^* para todo a en A .
• 1 + ( a ^* ) a ≤ a ^* para todo a en A .
• Si a y x están en A de tal manera que ax ≤ x , entonces a ^* x ≤ x
• Si a y x están en A de tal manera que xa ≤ x , entonces x ( a ^* ) ≤ x ^{[ 7 ]}

Intuitivamente, se puede 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 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 de lenguajes 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 expresiones regulares son iguales si describen el mismo lenguaje . Entonces A forma un álgebra de Kleene. De hecho, se trata de un álgebra de Kleene libre , ya 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 Σ 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 , y también la operación estrella de Kleene aplicada a cualquier elemento de A. Obtenemos un álgebra de Kleene A donde 0 es el conjunto vacío y 1 es 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 sea 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 }. Una construcción análoga puede realizarse 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 , definimos V + W como la suma de los dos subespacios, y 0 como el subespacio trivial {0}. Definimos V · W = span {v · w | v ∈ V, w ∈ W} , el espacio vectorial generado por el producto de vectores de V y W respectivamente. Definimos 1 = span {I} , el espacio vectorial generado por la unidad del álgebra. La clausura de V es la suma directa de todas las potencias de V.

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

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.

Cada álgebra booleana con operaciones${\displaystyle \lor }$y${\displaystyle \land }$se convierte en un álgebra de Kleene si usamos${\displaystyle \lor }$para +,${\displaystyle \land }$para · y establecer un ^* = 1 para todos los a .

Se puede usar un álgebra de Kleene bastante diferente para implementar el algoritmo de Floyd-Warshall , que calcula la longitud del camino más corto para cada par de vértices de un grafo dirigido ponderado , mediante el algoritmo de Kleene , que calcula una expresión regular para cada par de estados de un autómata finito determinista . Usando la recta real extendida , tomamos a + b como el mínimo de a y b y ab como la suma ordinaria de a y b (donde la suma de +∞ y −∞ se define 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 considerarse entonces como un autómata finito determinista, donde cada transición está etiquetada por su peso. Para cualesquiera dos nodos de un grafo (estados del autómata), las expresiones regulares calculadas a partir del algoritmo de Kleene se evalúan, en esta álgebra de Kleene en particular, como la longitud del camino más corto entre los nodos. ^{[ 8 ]}

El cero es el elemento más pequeño: 0 ≤ a para todo a en A.

La suma a + b es la cota superior mínima 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 ₁ + ... + a _n es la cota superior mínima 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 .

Respecto a la operación estrella, tenemos

• 0 ^* = 1 y 1 ^* = 1,
• a ≤ b implica a ^* ≤ b ^* (monotonicidad),
• a ⁿ ≤ a ^* para cada número natural n , donde a ⁿ se define como la multiplicación n veces de a ,
• ( a ^* )( a ^* ) = a ^* ,
• ( a ^* ) ^* = a ^* ,
• 1 + a ( a ^* ) = a ^* = 1 + ( a ^* ) a ,
• ax = xb implica ( a ^* ) x = x ( b ^* ),
• (( ab ) ^* ) a = a (( ba ) ^* ),
• ( a + b ) ^* = a ^* ( b ( a ^* )) ^* , y
• pq = 1 = qp implica q ( a ^* ) p = ( qap ) ^* . ^{[ 9 ]}

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 de n × 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. ^{[ 10 ] [ 11 ]} Aunque no definió las álgebras de Kleene, pidió un procedimiento de decisión para la equivalencia de expresiones regulares. ^{[ 12 ]} Redko demostró que ningún conjunto finito de axiomas ecuacionales puede caracterizar el álgebra de lenguajes regulares. ^{[ 13 ]} Salomaa dio axiomatizaciones completas de esta álgebra, sin embargo, dependiendo de reglas de inferencia problemáticas. ^{[ 14 ]} 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 , ^{[ 15 ]} sin embargo, la mayor parte de su tratamiento fue infinitario. En 1981, Kozen dio un sistema deductivo ecuacional infinitario completo para el álgebra de lenguajes regulares. ^{[ 16 ]} 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 deduce de los axiomas anteriores . ^{[ 17 ]}

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. Este cuasi-inverso no es necesariamente único. ^{[ 18 ] [ 19 ]} 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. ^{[ 19 ]}

Los semianillos cerrados y las álgebras de Kleene aparecen en los problemas de caminos algebraicos , una generalización del problema del camino más corto . ^{[ 19 ]}

• Álgebra de acción
• Estructura algebraica
• Estrella Kleene
• Expresión regular
• Semianillo estrellado
• Álgebra de valuación

• Kozen, Dexter . "CS786 Primavera 04, Introducción al álgebra de Kleene" .
• Peter Höfner (2009). Cálculos algebraicos para sistemas híbridos . BoD – Books on Demand. pp. 10–13 . ISBN  978-3-8391-2510-6.La introducción de este libro repasa los avances en el campo del álgebra de Kleene realizados en los últimos 20 años, que no se tratan en el artículo anterior.