Order Theory/Series-parallel order

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Definition (parallel order):

Let be a family of ordered sets, and define . Then the parallel order on is defined to be the order

.

Definition (parallel composition):

Let be a family of ordered sets, and define . Then the pair , where is the parallel order on , is called the parallel composition of the sets .

Definition (series order):

Let be a preordered set, and let be a family of ordered sets over . The series order on induced by is the order on given by

.

Definition (series composition):

Let be a preordered set, and let be a family of ordered sets, and define . Then the pair , where is the series order on , is called the series composition of the sets over .

Definition (series-parallel order):

A series-parallel order is the order of an ordered set that arises from a family of singleton ordered sets (the order being the order that turns into a poset) by applying parallel composition and series composition over a finite number of times.