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

Функция 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 имеет бесконечно много неподвижных точек, но не имеет хотя бы одной.

Приложения

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

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

Иммерман ^[1]^[2] и Вардите ^[3] независимо друг от друга показали описательную сложности результат , что полиномиальное время вычисляемые свойства из линейно упорядоченных структур определимы в 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 .

См. Также

Примечания

^ Н. Иммерман, Реляционные запросы, вычислимые за полиномиальное время, Информация и управление 68 (1–3) (1986) 86–104.
^ Иммерман, Нил (1982). «Реляционные запросы, вычислимые за полиномиальное время». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 147–152. DOI : 10.1145 / 800070.802187 . Пересмотренная версия в Information and Control , 68 (1986), 86–104.
Перейти ↑ Vardi, Moshe Y. (1982). «Сложность языков реляционных запросов». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 137–146. DOI : 10.1145 / 800070.802186 .

Ссылки

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

[1] Н. Иммерман, Реляционные запросы, вычислимые за полиномиальное время, Информация и управление 68 (1–3) (1986) 86–104.

[2] Иммерман, Нил (1982). «Реляционные запросы, вычислимые за полиномиальное время». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 147–152. DOI : 10.1145 / 800070.802187 . Пересмотренная версия в Information and Control , 68 (1986), 86–104.

[3] Перейти ↑ Vardi, Moshe Y. (1982). «Сложность языков реляционных запросов». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 137–146. DOI : 10.1145 / 800070.802186 .

[1]