Prefix order

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical systems as a set of functions from time (a totally-ordered set) to some phase space. In this case, the elements of the set are usually referred to as executions of the system. The name prefix order stems from the prefix order on words, which is a special kind of substring relation and, because of its discrete character, a tree.

In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical systems as a set of functions from time (a totally-ordered set) to some phase space. In this case, the elements of the set are usually referred to as executions of the system. The name prefix order stems from the prefix order on words, which is a special kind of substring relation and, because of its discrete character, a tree. if a ≤ b and b ≤ a then a = b (antisymmetry); if a ≤ b and b ≤ c then a ≤ c (transitivity); if a ≤ c and b ≤ c then a ≤ b or b ≤ a (downward totality). While between partial orders it is usual to consider order-preserving functions, the most important type of functions between prefix orders are so-called history preserving functions. Given a prefix ordered set P, a history of a point p∈P is the (by definition totally ordered) set p− = {q | q ≤ p}. A function f: P → Q between prefix orders P and Q is then history preserving if and only if for every p∈P we find f(p−) = f(p)−. Similarly, a future of a point p∈P is the (prefix ordered) set p+ = {q | p ≤ q} and f is future preserving if for all p∈P we find f(p+) = f(p)+. Every history preserving function and every future preserving function is also order preserving, but not vice versa. In the theory of dynamical systems, history preserving maps capture the intuition that the behavior in one system is a refinement of the behavior in another. Furthermore, functions that are history and future preserving surjections capture the notion of bisimulation between systems, and thus the intuition that a given refinement is correct with respect to a specification. The range of a history preserving function is always a prefix closed subset, where a subset S ⊆ P is prefix closed if for all s,t ∈ P with t∈S and s≤t we find s∈S.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1295264631 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001295264631 · captured 1749744979.0 · version history

Cite this page as: encyclopegia.org, “Prefix order”, snapshot enwiki-001295264631. https://encyclopegia.org/a/prefix-order

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.