Compositions of pattern restricted sets of permutations.
Michael Albert, Robert E. L. Aldred, Mike Atkinson, Hans P. van Ditmarsch, Chris C. Handley, Derek Holton, D. J. McCaughan · 2007
The composition of two pattern restricted classes X,Y is the set of all permutation products ## where # X,# Y . This set is also defined by pattern restrictions. Examples are given where this set of restrictions is finite and where it is infinite. The composition operation is studied in terms of machines that sort and generate permutations. The theory is then applied to a multistage sorting network where each stage can exchange any number of adjacent disjoint pairs.