On a characterization of pushdown permuters

Shyamasundar, R. K. (1982) On a characterization of pushdown permuters Theoretical Computer Science, 17 (3). pp. 333-341. ISSN 0304-3975

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/0...

Related URL: http://dx.doi.org/10.1016/0304-3975(82)90029-9


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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:56602
Deposited On:24 Aug 2011 10:55
Last Modified:24 Aug 2011 10:55

Repository Staff Only: item control page