A Study of Permutations Permissible by LIFO Service Disciplines

Abstract

We study permutations of the job order performed by various LIFO service disciplines. The sets of such permutations are shown to be equivalent to sets of string permutations with simple characteristics. In particular, it is easy to test whether a given permutation belongs to these sets. Several algorithms that efficiently perform such tests are presented. (Also cross-referenced as UMIACS-TR-98-65)