Pořadí předpony - Prefix order

V matematice , zejména v teorii objednávek , prefixová uspořádaná množina zevšeobecňuje intuitivní pojetí stromu zavedením možnosti nepřetržitého postupu a nepřetržitého větvení. Pořadí přirozených předpon se často vyskytuje, když uvažujeme o dynamických systémech jako o sadě funkcí od času ( zcela uspořádaná množina ) po nějaký fázový prostor . V tomto případě se prvky sady obvykle označují jako provedení systému.

Pořadí předpony jmen vychází z pořadí předpony slov, což je zvláštní druh relace podřetězce a kvůli svému diskrétnímu charakteru strom.

Formální definice

Předpona příkaz je binární relace „≤“ nad nastavenou P , který je antisymetrická , tranzitivní , reflexivní a dolů celkem , tedy pro všechny a , b , a c v P , jsme, že:

• a ≤ a (reflexivita);
• pokud a ≤ b a b ≤ a, pak a = b (antisymetrie);
• pokud a ≤ b a b ≤ c pak a ≤ c (tranzitivita);
• pokud a ≤ c a b ≤ c, pak a ≤ b nebo b ≤ a (součet dolů).

Funkce mezi objednávkami předpon

Zatímco mezi dílčími objednávkami je obvyklé uvažovat o funkcích zachovávajících pořadí , nejdůležitějším typem funkcí mezi objednávkami předpony jsou takzvané funkce zachovávající historii . Vzhledem k předpřipravené množině P je historie bodu p ∈ P (podle definice zcela uspořádaná) množina p - = { q | q ≤ p }. Funkce f  : P → Q mezi prefixovými příkazy P a Q je pak zachováním historie, právě když pro každé p ∈ P najdeme f ( p -) = f ( p ) -. Podobně budoucnost bodu p ∈ P je (uspořádaná předpona) množina p + = { q | p ≤ q } af je budoucí zachování, pokud pro všechna p ∈ P najdeme f ( p +) = f ( p ) +.

Každá funkce pro zachování historie a každá budoucí funkce pro zachování je také ochrana pořadí, ale ne naopak. V teorii dynamických systémů zachycují mapy uchovávající historii intuici, že chování v jednom systému je vylepšení chování v jiném systému. Kromě toho funkce, které představují historii a budoucnost zachovávající surjekce, zachycují pojem bisimulace mezi systémy, a tedy intuici, že dané zpřesnění je správné s ohledem na specifikaci.

Řada z funkce zachování historie je vždy prefix uzavřená podmnožina, kde podmnožina S ⊆ P je prefix uzavřen , jestliže pro všechny s, t ∈ P s t∈S a s≤t najdeme s∈S .

Produkt a spojení

Vezmeme-li historii zachovávající mapy jako morfismy v kategorii objednávek předpony, vede to k představě o produktu, který není kartézským součinem dvou objednávek, protože kartézský součin není vždy objednávkou předpony. Místo toho to vede k libovolnému prokládání původních objednávek předpon. Spojení dvou objednávek předpony je disjunktní spojení , jako je tomu u částečných objednávek.

Izomorfismus

Jakákoli funkce zachování historie bijektivů je izomorfismus řádu . Dále, pokud pro danou prefixovou objednanou množinu P sestrojíme množinu P- ≜ {p- | p∈ P} zjistíme, že tato množina je předponou seřazenou podle podmnožinového vztahu ⊆, a dále, že funkce max: P- → P je izomorfismus, kde max (S) vrací pro každou množinu S∈P- maximální prvek z hlediska objednávky na P (tj. max (p-) ≜ p ).

Reference

• Cuijpers, Pieter (2013). „Objednávky s předponou jako obecný model dynamiky“ (PDF) . Sborník příspěvků z 9. mezinárodního semináře o vývoji výpočetních modelů (DCM) . s. 25–29.
• Cuijpers, Pieter (2013). "Kategorický limit posloupnosti dynamických systémů". EPTCS 120: Sborník EXPRESS / SOS 2013 . str. 78–92. doi : 10,4204 / EPTCS.120.7 .
• Ferlez, James; Cleaveland, Rance; Marcus, Steve (2014). "Zobecněné synchronizační stromy". LLNCS 8412: Proceedings of FOSSACS'14 . 304–319. doi : 10,1007 / 978-3-642-54830-7_20 .