Kybernetika 41 no. 4, 531-537, 2005

Self-reproducing pushdown transducers

Alexander Meduna and Luboš Lorenc

Abstract:

After a translation of an input string, $x$, to an output string, $y$, a self-reproducing pushdown transducer can make a self-reproducing step during which it moves $y$ to its input tape and translates it again. In this self-reproducing way, it can repeat the translation $n$-times for any $n \ge 1$. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.