A Counterexample to Reingold’s Pushdown Permuter Characterization Theorem

There is a well-known class of algorithms for permuting symbols which has been formally characterized by a device called a pushdown permuter. A theorem attempting to characterize the type of permutations that can be achieved by a pushdown permuter has appeared in the literature. This paper presents a counterexample to this theorem.