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, de acuerdo con 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 2 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 suelen tener propiedades deseables que los puntos fijos arbitrarios no tienen.
En lógica matemática e informática , el punto menos fijo está relacionado con la elaboración de definiciones recursivas (consulte la teoría de dominio y / o semántica denotacional para obtener 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 de
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, la componente fuertemente conectada de v es la intersección de esos dos puntos menos fijos.
Dejar ser una gramática libre de contexto . El conjuntode símbolos que produce la cadena vacía se puede obtener como el punto mínimo fijo de la función , definido como , dónde denota el conjunto de poder de.
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
Notas
- ^ N. Immerman, Consultas relacionales computables en tiempo polinomial, Información y control 68 (1-3) (1986) 86-104.
- ^ 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.
- ^ 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.