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.
Reversible Pushdown Transducers / B. Guillon, M. Kutrib, A. Malcher, L. Prigioniero (LECTURE NOTES IN COMPUTER SCIENCE). - In: Developments in Language Theory : proceedings / [a cura di] M. Hoshi, S. Seki. - [s.l] : Springer Verlag, 2018. - ISBN 9783319986531. - pp. 354-365 (( Intervento presentato al 22. convegno International Conference on Developments in Language Theory tenutosi a Tokyo nel 2018.
|Titolo:||Reversible Pushdown Transducers|
|Parole Chiave:||Theoretical Computer Science; Computer Science (all)|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2018|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-319-98654-8_29|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|