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, c13-math-0001 means that the statement c13-math-0002 should be executed after the statement c13-math-0003. The concurrent programming languages introduce an additional parallel operator c13-math-0004 to model parallel execution of activities. Consider the following programming expression:

In this program, is always executed ...

Get Introduction to Lattice Theory with Computer Science Applications now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.