В математике , особенно в теории порядка , упорядоченный набор префиксов обобщает интуитивную концепцию дерева , вводя возможность непрерывного прогресса и непрерывного ветвления. Естественные порядки префиксов часто возникают при рассмотрении динамических систем как набора функций от времени ( полностью упорядоченный набор ) до некоторого фазового пространства . В этом случае элементы набора обычно называют исполнениями системы.
Порядок префиксов имен проистекает из порядка префиксов в словах, который представляет собой особый вид отношения подстроки и, из-за его дискретного характера, представляет собой дерево.
Формальное определение
Порядок префикса является бинарным отношением «≤» по множеству P , который является антисимметричным , транзитивным , рефлексивным и вниз общее , то есть, для всех в , б и с в Р , имеем:
- a ≤ a (рефлексивность);
- если a ≤ b и b ≤ a, то a = b (антисимметрия);
- если a ≤ b и b ≤ c, то a ≤ c (транзитивность);
- если a ≤ c и b ≤ c, то a ≤ b или b ≤ a (нисходящая совокупность).
Функции между порядками префиксов
В то время как между частичными порядками обычно рассматриваются функции , сохраняющие порядок , наиболее важным типом функций между префиксными порядками являются так называемые функции сохранения истории . Учитывая префикс упорядоченного множества P , а историю точечного р ∈ P является (по определению упорядоченным) множество р - = { д | q ≤ p }. Функция F : P → Q между префиксом порядков P и Q тогда история сохранения , если и только если для каждого р ∈ 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, Питер (2013). «Префиксные приказы как общая модель динамики» (PDF) . Материалы 9-го международного семинара по разработке вычислительных моделей (DCM) . С. 25–29.
- Cuijpers, Питер (2013). «Категориальный предел последовательности динамических систем». EPTCS 120: Труды EXPRESS / SOS 2013 . С. 78–92. DOI : 10,4204 / EPTCS.120.7 .
- Ферлез, Джеймс; Кливленд, Рэнс; Маркус, Стив (2014). «Обобщенные деревья синхронизации». LLNCS 8412: Труды FOSSACS'14 . С. 304–319. DOI : 10.1007 / 978-3-642-54830-7_20 .