Punto mínimo fijo

La función f ( x ) =  x ²  - 4 tiene dos puntos fijos, que se muestran como la intersección con la línea azul; su menos uno está en medio -  √ 17 /2.

En la teoría del orden , una rama de las matemáticas , el punto menos fijo ( lfp o LFP , a veces también el punto fijo más pequeño ) de una función de un conjunto parcialmente ordenado a sí mismo es el punto fijo que es menor que cada otro punto fijo, según el orden del poset. Una función no necesita tener un punto mínimo fijo, pero si lo tiene, entonces el punto menos fijo es único.

Por ejemplo, con el orden habitual de los números reales , el punto mínimo fijo de la función real f ( x ) = x ² es x = 0 (ya que el único otro punto fijo es 1 y 0 <1). En contraste, f ( x ) = x + 1 no tiene puntos fijos en absoluto, por lo que no tiene al menos uno, y f ( x ) = x tiene infinitos puntos fijos, pero no tiene al menos uno.

Aplicaciones

Muchos teoremas del punto fijo producen algoritmos para localizar el punto menos fijo. Los puntos mínimos fijos a menudo tienen propiedades deseables que los puntos fijos arbitrarios no tienen.

En lógica matemática y ciencias de la computación , el punto menos fijo está relacionado con la elaboración de definiciones recursivas (ver teoría de dominio y / o semántica denotacional para más detalles).

Immerman ^{[1] [2]} y Vardi ^[3] mostraron independientemente el resultado de complejidad descriptiva de que las propiedades computables en tiempo polinómico de estructuras ordenadas linealmente son definibles en FO (LFP) , es decir, en lógica de primer orden con un operador de punto fijo mínimo. Sin embargo, FO (LFP) es demasiado débil para expresar todas las propiedades de tiempo polinómico de estructuras desordenadas (por ejemplo, que una estructura tiene un tamaño uniforme ).

Ejemplos

Deje que G = ( V , A ) un grafo dirigido y v sea un vértice. El conjunto de nodos accesibles desde v se puede definir como el conjunto S que es el punto fijo mínimo para la propiedad: v pertenece a S y si w pertenece a S y hay una arista de w a x , entonces x pertenece a S . El conjunto de nodos que son co-accesibles desde v está definido por un punto mínimo de fijación similar. Por un lado elcomponente fuertemente conectado de v es la intersección de esos dos puntos fijos mínimos.

Dejar ${\displaystyle G=(V,\Sigma ,R,S_{0})}$ser una gramática libre de contexto . El conjunto${\displaystyle E}$de símbolos que produce la cadena vacía ${\displaystyle \varepsilon }$ se puede obtener como el punto mínimo fijo de la función ${\displaystyle f:\wp (V)\to \wp (V)}$, definido como ${\displaystyle f(X)=\{S\in V:\;S\in X{\text{ or }}(S\to \varepsilon )\in R{\text{ or }}(S\to S^{1}\dots S^{n})\in R{\text{ and }}S^{i}\in X{\text{, for all }}i\}}$, donde ${\displaystyle \wp (V)}$denota el conjunto de poder de${\displaystyle V}$.

Puntos fijos más grandes

También se pueden determinar los puntos fijos más grandes, pero se utilizan con menos frecuencia que los puntos fijos mínimos. Sin embargo, en informática , de forma análoga al punto menos fijo, dan lugar a corecursion y codata .

Ver también

• Punto fijo
• Teorema del punto fijo de Kleene
• Teorema de Knaster-Tarski

Notas

1. N. Immerman, Consultas relacionales computables en tiempo polinomial, Información y control 68 (1-3) (1986) 86-104.
2. Immerman, Neil (1982). "Consultas relacionales computables en tiempo polinomial". STOC '82: Actas del decimocuarto simposio anual ACM sobre teoría de la computación . págs. 147-152. doi : 10.1145 / 800070.802187 . Versión revisada en Information and Control , 68 (1986), 86-104.
3. Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales". STOC '82: Actas del decimocuarto simposio anual ACM sobre teoría de la computación . págs. 137-146. doi : 10.1145 / 800070.802186 .

Referencias

• Immerman, Neil . Complejidad descriptiva , 1999, Springer-Verlag.
• Libkin, Leonid . Elementos de la teoría de modelos finitos , 2004, Springer.