Journalartikel

Jahr der Veröffentlichung: 2019

Seiten: 111-126

Zeitschrift: Theoretical Computer Science

Bandnummer: 787

ISSN: 0304-3975

eISSN: 1879-2294

Open Access Status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2019.06.021

Verlag: Elsevier

Abstract: 
Finite state machines are investigated towards their ability to reversibly compute transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are backward deterministic and hence are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to three types of length-preserving transductions as well as to the property of working reversibly. It is possible to settle all inclusion relations between these families of transductions even with injective witness transductions. Furthermore, the standard closure properties and decidability questions are investigated. It turns out that the non-closure under almost all operations can be shown, whereas all decidability questions can be answered in polynomial time. Finally, the concept of reversibility is extended to a broader view of reversibility and an infinite and dense hierarchy with respect to the grade of reversibility is obtained. (C) 2019 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Kutrib, M., Malcher, A. and Wendlandt, M. (2019) Transducing reversibly with finite state machines, Theoretical Computer Science, 787, pp. 111-126. https://doi.org/10.1016/j.tcs.2019.06.021

APA-Zitierstil: Kutrib, M., Malcher, A., & Wendlandt, M. (2019). Transducing reversibly with finite state machines. Theoretical Computer Science. 787, 111-126. https://doi.org/10.1016/j.tcs.2019.06.021