Cel mai mic punct fix - Least fixed point

Funcția f ( x ) =  x ²  - 4 are două puncte fixe, arătate ca intersecție cu linia albastră; cel puțin unul sau este la 1/2 -  √ de 17 /2.

În teoria ordinii , o ramură a matematicii , cel mai puțin punct fix ( lfp sau LFP , uneori și cel mai mic punct fix ) al unei funcții dintr-un set parțial ordonat la sine este punctul fix care este mai mic decât celălalt punct fix, conform ordinea pozetului. O funcție nu trebuie să aibă un punct cel puțin fix, dar dacă are, cel mai puțin punct fix este unic.

De exemplu, cu ordinea obișnuită pe numerele reale , cel mai mic punct fix al funcției reale f ( x ) = x ² este x = 0 (deoarece singurul alt punct fix este 1 și 0 <1). În schimb, f ( x ) = x + 1 nu are deloc puncte fixe, deci nu are cel puțin unul, iar f ( x ) = x are infinit de multe puncte fixe, dar nu are cel puțin unul.

Aplicații

Multe teoreme cu punct fix dau algoritmi pentru localizarea celui mai puțin punct fix. Cele mai puține puncte fixe au deseori proprietăți dorite, pe care punctele fixe arbitrare nu le au.

În logica matematică și informatică , cel mai puțin punct fix este legat de realizarea definițiilor recursive (a se vedea teoria domeniului și / sau semantica denotațională pentru detalii).

Immerman și Vardi a arătat în mod independent complexitatea descriptiv rezultat faptul că polinomul timp proprietățile calculabile ale ordonate liniar structuri sunt definibile în FO (LFP) , adică în logica de ordinul întâi cu un operator punct cel fix. Cu toate acestea, FO (LFP) este prea slab pentru a exprima toate proprietățile polinomiale în timp ale structurilor neordonate (de exemplu, o structură are dimensiuni egale ).

Exemple

Fie G = ( V , A ) un grafic direcționat și v un vârf. Setul de noduri accesibile din v poate fi definit ca setul S care este cel puțin un punct fix pentru proprietatea: v aparține S și dacă w aparține S și există o margine de la w la x , atunci x aparține S . Setul de noduri care sunt co-accesibile din v este definit de un punct de fixare cel mai mic similar. Pe de o parte, componenta puternic conectată a lui v este intersecția celor două puncte cele mai puțin fixe.

Să fie o gramatică fără context . Setul de simboluri care produce șirul gol poate fi obținut ca cel mai mic punct fix al funcției , definit ca , unde denotă setul de putere al . ${\ displaystyle G = (V, \ Sigma, R, S_ {0})}$${\ displaystyle E}$ ${\ displaystyle \ varepsilon}$${\ displaystyle f: \ wp (V) \ to \ wp (V)}$${\ 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}) \ în R {\ text {și}} S ^ {i} \ în X {\ text {, pentru toți}} i \}}$${\ displaystyle \ wp (V)}$${\ displaystyle V}$

Cele mai mari puncte fixe

Se pot determina și cele mai mari puncte fixe, dar sunt mai puțin utilizate decât punctele fixe cele mai mici. Cu toate acestea, în informatică , în mod analog punctului cel mai puțin fix, dau naștere la corecursie și codate .

Vezi si

• Punct fix
• Teorema punctului fix Kleene
• Teorema Knaster – Tarski

Note

Referințe

• Immerman, Neil . Complexitate descriptivă , 1999, Springer-Verlag.
• Libkin, Leonid . Elemente ale teoriei modelelor finite , 2004, Springer.