Journalartikel

Jahr der Veröffentlichung: 2021

Zeitschrift: Information and Computation

Bandnummer: 281

ISSN: 0890-5401

eISSN: 1090-2651

Open Access Status: Green

DOI Link: https://doi.org/10.1016/j.ic.2021.104813

Verlag: Elsevier

Abstract: 
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. (C) 2021 Elsevier Inc. All rights reserved.

Harvard-Zitierstil: Guillon, B., Kutrib, M., Malcher, A. and Prigioniero, L. (2021) Reversible pushdown transducers, Information and Computation, 281, Article 104813. https://doi.org/10.1016/j.ic.2021.104813

APA-Zitierstil: Guillon, B., Kutrib, M., Malcher, A., & Prigioniero, L. (2021). Reversible pushdown transducers. Information and Computation. 281, Article 104813. https://doi.org/10.1016/j.ic.2021.104813