On a characterization of pushdown permuters

Abstract

In the literature, there is a class of algorithms for permuting the symbols of an input string, that uses a single pushdown stack and a finite number of random access storage cells, that has been formalized by a device called pushdown permuter. This paper establishes a theorem that characterizes the type of permutations that can be obtained by a pushdown permuter. As a corollary of this theorem, it is established that there is no algorithm in the above mentioned class of algorithms that can translate arithmetic expressions from infix to prefix.