On a characterization of pushdown permuters |
| |
Authors: | RK Shyamasundar |
| |
Affiliation: | National Centre for Software Development and Computing Techniques, Tata Institute of Fundamental Research, Bombay 400 005, India |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|