Najmniejszy stały punkt

Funkcja f ( x ) = x ² − 4 ma dwa stałe punkty, pokazane jako przecięcie z niebieską linią; jego najmniejsza wynosi 1/2 - √ 17/2 .

W teorii porządku , gałęzi matematyki , najmniej stałym punktem ( lfp lub LFP , czasem także najmniejszym stałym punktem ) funkcji z częściowo uporządkowanego zbioru do samej siebie jest ten stały punkt , który jest mniejszy od każdego innego stałego punktu, zgodnie z kolejność pozy. Funkcja nie musi mieć najmniejszego punktu stałego, ale jeśli tak, to najmniejszy punkt stały jest unikalny.

Na przykład, przy zwykłej kolejności liczb rzeczywistych , najmniej stałym punktem funkcji rzeczywistej f ( x ) = x ² jest x = 0 (ponieważ jedynym innym stałym punktem jest 1 i 0 < 1). W przeciwieństwie do tego, f ( x ) = x + 1 w ogóle nie ma punktów stałych, więc nie ma najmniejszego punktu, a f ( x ) = x ma nieskończenie wiele punktów stałych, ale nie ma najmniejszego jednego.

Przykłady

Niech będzie skierowanym wykresem i będzie wierzchołkiem $. sol = ( V , ZA )$ $V$ Zbiór wierzchołków dostępnych z $V)}$ zdefiniować jako najmniejszy stały punkt funkcji $($ ${\ Displaystyle f: \ wp (V) \ do \ wp$ , zdefiniowany jako ${\ Displaystyle f (X) = \ {v \} \ kubek \ {x \ w V: {\ tekst {dla niektórych}} w \ w X {\ tekst {jest łuk od}} w {\ tekst { do }} x \}.}$ Zbiór wierzchołków, które są współdostępne z $jest$ przez podobny najmniejszy stały punkt. Silnie połączony składnik v $\ displaystyle v}$ jest przecięciem tych dwóch najmniej stałych punktów.

Niech będzie gramatyką bezkontekstową ${\ Displaystyle G = (V, \ Sigma, R, S_ {0})$ } Zbiór symboli, który tworzy ciąg $,$ $można otrzymać$ najmniejszy stały punkt funkcji ${\ Displaystyle f: \ wp (V) \ do \ wp (V)}$ , zdefiniowany jako ${\ Displaystyle f (X) = \ {S \ w V: \; S \ w X {\ tekst {lub}} (S \ do \ varepsilon) \ w R {\ tekst {lub}} (S \ do S ^{1}\dots S^{n})\in R{\text{ i }}S^{i}\in X{\text{, dla wszystkich }}i\}} ,$ gdzie $displaystyle \ wp (V)}$ ${$ ${\ displaystyle V}$ oznacza zestaw mocy V .

Aplikacje

Wiele twierdzeń o punkcie stałym daje algorytmy lokalizowania najmniejszego punktu stałego. Najmniej stałych punktów często ma pożądane właściwości, których nie mają dowolne punkty stałe.

Semantyka denotacyjna

Częściowe zamówienie na

{\ Displaystyle \ mathbb {Z} _ {\ bot}}

W informatyce podejście semantyki denotacyjnej wykorzystuje najmniej stałych punktów, aby uzyskać z danego tekstu programu odpowiednią funkcję matematyczną, zwaną jego semantyką. $.$ tym celu wprowadza się sztuczny obiekt matematyczny, oznaczający wyjątkową wartość „niezdefiniowany” Biorąc pod uwagę np. typ danych programu int , jego matematyczny odpowiednik jest zdefiniowany jako ${\ Displaystyle \ mathbb {Z} _ {\ bot} = \ mathbb {Z} \ kubek \ {\ bot \};} jest to zestaw częściowo uporządkowany przez zdefiniowanie ⊥$ ⊏ $Displaystyle \ bot \ sqsubset n}$ dla każdego $\ Displaystyle$ pozwalając dowolnym dwóm różnym członom $n, m \ in \ mathbb {Z}}$ być nieporównywalnymi wrt $Displaystyle \ \ sqsubset }$ , patrz obrazek.

Semantyka definicji programu int f(int n){...} jest pewną funkcją matematyczną ${\ Displaystyle f: \ mathbb {Z} _ {\ bot} \ do \ mathbb {Z} _ {\ bot}.} Jeśli$ definicja programu f nie kończy się dla jakiegoś wejścia n , można to wyrazić matematycznie jako ${\ Displaystyle f (n) = \ bot.}$ Zbiór wszystkich funkcji matematycznych jest częściowo uporządkowany przez zdefiniowanie ${\ Displaystyle f \ sqsubseteq g}$ $)$ jeśli dla każdego relacja fa $sqsubseteq g (n)}$ ${\ displaystyle g (n).}$ jeśli $n$ lub Na przykład semantyka wyrażenia x + x / x jest mniej zdefiniowany niż x + 1 , ponieważ to pierwsze, ale nie drugie, odwzorowuje na $displaystyle \ bot,}$ $\$ i zgadzają się inaczej.

Biorąc pod uwagę jakiś tekst programu f , jego matematyczny odpowiednik otrzymuje się jako najmniej stały punkt pewnego odwzorowania funkcji na funkcje, które można uzyskać przez „tłumaczenie” f . Na przykład definicja C

       0         int  fact  (  int  n  )  {  if  (  n  ==  )  return  1  ;  w przeciwnym razie  zwróć  n  *  fakt  (  n  -1  );  }

jest tłumaczony na mapowanie

{\ Displaystyle F: (\ mathbb {Z} _ {\ bot} \ do \ mathbb {Z} _ {\ bot}) \ do ( \mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),}

zdefiniowany jako

{\ Displaystyle (F (f)} (n) = {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} n = 0, \\ n \ cdot f (n-1) i {\ tekst {jeśli}} n\neq \bot {\text{ i }}n\neq 0,\\\bot &{\text{if }}n=\bot .\\\end{przypadki}}}

Odwzorowanie jest zdefiniowane w sposób nierekurencyjny, chociaż $fakt$ został rekurencyjnie. Z pewnymi ograniczeniami (patrz twierdzenie Kleene'a o punkcie stałym $\ operatorname {fakt}}$ , które są spełnione w przykładzie, koniecznie ma najmniejszy punkt stały, $displaystyle$ , czyli ${\ Displaystyle (F (\ operatorname {fakt})} (n) = \ operatorname {fakt} (n)}$ dla wszystkich ${\ Displaystyle n \ in \ mathbb {Z} _ {\ bot}}$ . Jest to możliwe do pokazania

{\ Displaystyle \ nazwa operatora {fakt} (n) = {\ rozpocząć {przypadki} n! & {\ tekst {jeśli}} n \ geq 0, \\\ bot & {\ tekst {jeśli}} n <0 {\ tekst{ lub }}n=\bot .\end{przypadki}}}

Większym stałym punktem jest np. funkcja ${\ displaystyle \ operatorname {fakt} _ {0},}$ ${\ displaystyle F}$ przez fa

{\ Displaystyle \ operatorname {fakt} _ {0} (n) = {\ rozpocząć {przypadki} n! & {\ tekst {jeśli}} n \ geq 0 ,\\0&{\text{if }}n<0,\\\bot &{\text{if }}n=\bot ,\end{przypadki}}}

0 jednak ta funkcja nie odzwierciedla prawidłowo zachowania powyższego tekstu programu dla ujemnego ${\ displaystyle n;}$ np. call fact (-1) w ogóle się nie zakończy, nie mówiąc już o powrocie . Tylko najmniej ustalony punkt, $może$ być rozsądnie użyty jako semantyczny program matematyczny.

Złożoność opisowa

Immerman i Vardi niezależnie wykazali wynik złożoności opisowej , że obliczalne w czasie wielomianowym właściwości struktur uporządkowanych liniowo są definiowalne w FO(LFP) , tj. w logice pierwszego rzędu z operatorem najmniejszego punktu stałego. Jednak FO (LFP) jest zbyt słaby, aby wyrazić wszystkie właściwości struktur nieuporządkowanych w czasie wielomianowym (na przykład, że struktura ma parzysty rozmiar).

Największe punkty stałe

Można również określić największe punkty stałe. W przypadku liczb rzeczywistych definicja jest symetryczna z najmniej ustalonym punktem, ale w informatyce są one rzadziej stosowane niż najmniej ustalone punkty. W szczególności pozycje występujące w teorii dziedzin zwykle nie mają największego elementu, stąd może istnieć wiele wzajemnie nieporównywalnych maksymalnych punktów stałych, a największy punkt stały może nie istnieć. Aby rozwiązać ten problem, optymalny punkt stały został zdefiniowany jako najbardziej zdefiniowany punkt stały zgodny ze wszystkimi innymi punktami stałymi. Optymalny punkt stały istnieje zawsze i jest największym punktem stałym, jeśli istnieje największy punkt stały. Optymalny punkt stały umożliwia formalne badanie rekurencyjnych i współkursywnych , które nie zbiegają się z najmniejszym punktem stałym. Niestety optymalnym stałym punktem efektywnej definicji rekurencyjnej może być funkcja nieobliczalna, więc ma to głównie znaczenie teoretyczne.

Zobacz też

Notatki

Immerman, Neil . Opisowa złożoność , 1999, Springer-Verlag.
Libkin, Leonid . Elementy teorii modeli skończonych , 2004, Springer.