Introduction to Lattice Theory with Computer Science Applications

Chapter 13Tractable posets

13.1 Introduction

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.

13.2 Series–Parallel Posets

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 ...