So far, we have seen some efficient algorithms for determining characteristics of posets such as its width. However, there are no known efficient algorithms for some other important properties, such as the dimension, the number of ideals, and the number of linear extensions of a given poset. In these cases, we can study special classes of the poset for which there exist efficient algorithms for these computationally hard problems. In this chapter, we cover an important class of posets—two-dimensional posets and its special case series–parallel posets that arise frequently in computer science applications.

Traditional sequential programming languages provide a *series* operator ‘;’ to compose two statement or functions in a serial manner. Thus, means that the statement should be executed after the statement . The concurrent programming languages introduce an additional *parallel* operator to model parallel execution of activities. Consider the following programming expression:

In this program, is always executed ...

Start Free Trial

No credit card required