Префиксный порядок

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

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

Префиксный порядок — это бинарное отношение «≤» над множеством 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 ).

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