Порядок префиксов

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

имен Порядок префиксов происходит от порядка префиксов в словах, который представляет собой особый вид отношения подстроки и, из-за своего дискретного характера, является деревом.

Формальное определение

Префиксный порядок — это бинарное отношение «≤» над множеством P , которое является антисимметричным , транзитивным , рефлексивным и нисходящим тотальным , т. е. для всех a , b и c в P мы имеем следующее:

• а ≤ а (рефлексивность);
• если a ≤ b и b ≤ a, то a = b (антисимметрия);
• если a ⩽ b и b ⩽ c, то a ⩽ c (транзитивность);
• если a ⩽ c и b ⩽ c, то a ⩽ b или b ⩽ a (нисходящая совокупность).

Функции между префиксными ордерами

В то время как между частичными порядками обычно рассматривают функции сохранения порядка , наиболее важным типом функций между префиксными порядками являются так называемые функции сохранения истории . Для заданного префиксно упорядоченного множества P история — точки p ∈ P это (по определению полностью упорядоченное) множество p − = { q | q ≤ p }. Функция f : P → Q между префиксными порядками P и Q тогда сохраняет историю и только тогда, когда для каждого p ∈ P мы находим f ( p −) = f ( p )−. Аналогично, будущее точки p ∈ P — это (упорядоченное по префиксу) множество p + = { q | p ≤ q } и f сохраняет будущее, если для всех p ∈ P мы находим f ( p +) = f ( p )+.

Каждая функция сохранения истории и каждая функция сохранения будущего также являются сохранением порядка, но не наоборот.В теории динамических систем карты, сохраняющие историю, отражают интуитивное представление о том, что поведение в одной системе является уточнением поведения в другой. сохраняющие историю и будущее, Более того, функции, которые представляют собой сюръекции, отражают понятие бисимуляции между системами и, следовательно, интуицию о том, что данное уточнение правильно по отношению к спецификации.

Диапазон префиксно функции, сохраняющей историю, всегда представляет собой -замкнутое подмножество, где подмножество S ⊆ P является префиксно-замкнутым, если для всех s,t ∈ P с tεS и s≤t мы находим sεS .

Продукт и союз

Принятие карт, сохраняющих историю, в качестве морфизмов в категории префиксных порядков приводит к понятию продукта, который не является декартовым произведением двух порядков, поскольку декартово произведение не всегда является префиксным порядком. Вместо этого это приводит к произвольному чередованию исходных порядков префиксов. Объединение двух префиксных заказов является непересекающимся объединением , как и частичные заказы.

Изоморфизм

Любая биективная функция, сохраняющая историю, является порядковым изоморфизмом . Более того, если для данного префиксного упорядоченного множества P построить множество P- ≜ { p- | pε P} мы находим, что это множество является префиксно упорядоченным отношением подмножества ⊆, и, кроме того, что функция max: P- → P является изоморфизмом, где max(S) возвращает для каждого множества SεP — максимальный элемент в терминах порядка на P (т.е. max(p-) ≜ p ).

Ссылки

• Куиджперс, Питер (2013). «Префиксные приказы как общая модель динамики» (PDF) . Материалы 9-го Международного семинара по развитию вычислительных моделей (DCM) . стр. 25–29.
• Куиджперс, Питер (2013). «Категорический предел последовательности динамических систем» . EPTCS 120: Протоколы EXPRESS/SOS 2013 . 120 : 78–92. arXiv : 1307.7445 . дои : 10.4204/EPTCS.120.7 .
• Ферлез, Джеймс; Кливленд, Рэнс; Маркус, Стив (2014). «Обобщенные деревья синхронизации». Основы науки о программном обеспечении и вычислительных структур . Конспекты лекций по информатике. Том. 8412. стр. 304–319. дои : 10.1007/978-3-642-54830-7_20 . ISBN  978-3-642-54829-1 .