O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required