Наименьшая фиксированная точка - Least fixed point

Функция f ( x ) =  x ²  - 4 имеет две неподвижные точки, показанные как пересечение с синей линией; ее меньшей мере , один находится на 1/2 -  √ 17 /2.

В теории порядка филиала математики , по крайней мере , фиксированной точки ( LFP или LFP , иногда также наименьшая фиксированная точка ) в виде функции от частично упорядоченного множества к себе является фиксированной точкой , который меньше , чем друг с другом неподвижной точки, в соответствии с порядок посета. Функция не обязательно должна иметь наименьшую фиксированную точку, но если она есть, наименьшая фиксированная точка уникальна.

Например, при обычном порядке действительных чисел наименьшая фиксированная точка действительной функции f ( x ) = x ² - это x = 0 (поскольку единственная другая фиксированная точка - 1 и 0 <1). Напротив, f ( x ) = x + 1 вообще не имеет неподвижных точек, поэтому не имеет хотя бы одной, а f ( x ) = x имеет бесконечно много неподвижных точек, но не имеет хотя бы одной.

Приложения

Многие теоремы о фиксированной точке приводят к алгоритмам поиска наименьшей фиксированной точки. Наименее неподвижные точки часто имеют желаемые свойства, которых нет у произвольных неподвижных точек.

В математической логике и информатике наименьшая фиксированная точка связана с рекурсивными определениями (подробности см. В теории предметной области и / или денотационной семантике ).

Иммерман и Вардите независимо друг от друга показали описательную сложности результат , что полиномиальное время вычисляемые свойства из линейно упорядоченных структур определимы в FO (LFP) , то есть в логике первого порядка с оператором наималейшим неподвижной точки. Однако FO (LFP) слишком слаб, чтобы выразить все свойства полиномиального времени неупорядоченных структур (например, что структура имеет четный размер).

Примеры

Пусть G = ( V , A ) ориентированный граф и v вершина. Множество узлов , доступных из V может быть определен как множества S , которая является наименьшей неподвижной точкой для свойства: v принадлежит S , и если ш принадлежит S и есть ребро от ж к х , то х принадлежит S . Набор узлов, которые совместно доступны из v , определяется аналогичной наименьшей фиксированной точкой. С одной стороны, сильно компонента связности из V является пересечением этих двух фиксированных минимум точек.

Позвольте быть контекстно-свободной грамматики . Набор символов , который производит пустую строку может быть получен , как наименее фиксированной точка функции , определяется как , где обозначает набор мощности из . ${\ Displaystyle G = (V, \ Sigma, R, S_ {0})}$${\ displaystyle E}$ ${\ displaystyle \ varepsilon}$${\ Displaystyle е: \ WP (V) \ к \ WP (V)}$${\ displaystyle f (X) = \ {S \ in V: \; S \ in X {\ text {or}} (S \ to \ varepsilon) \ in R {\ text {или}} (S \ to S ^ {1} \ dots S ^ {n}) \ in R {\ text {and}} S ^ {i} \ in X {\ text {, для всех}} i \}}$${\ Displaystyle \ WP (V)}$${\ displaystyle V}$

Наибольшие фиксированные точки

Также можно определить наибольшие фиксированные точки, но они используются реже, чем наименее фиксированные точки. Однако в информатике они, как и наименьшая фиксированная точка, порождают corecursion и codata .

Смотрите также

• Фиксированная точка
• Теорема Клини о неподвижной точке
• Теорема Кнастера – Тарского

Ноты

Рекомендации

• Иммерман, Нил . Описательная сложность , 1999, Springer-Verlag.
• Либкин, Леонид . Элементы теории конечных моделей , 2004, Springer.