Reversible pushdown transducers

Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to four types of length-preserving transductions as well as to the property of working reversibly. It turns out that accurate to one case separating witness transductions can be provided. For the remaining case it is possible to establish the equivalence of both families by proving that stationary moves can always be removed in length-preserving reversible pushdown transductions.

Authors

• Bruno Guillon
• Martin Kutrib
• Andreas Malcher
• Luca Prigioniero

Keywords

• Pushdown transducers
• Reversible computations
• Computational capacity
• Transduction hierarchies