Journal article

Publication year: 2019

Pages: 111-126

Journal: Theoretical Computer Science

Volume number: 787

ISSN: 0304-3975

eISSN: 1879-2294

Open access status: Bronze

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

Publisher: 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 Citation style: 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 Citation style: 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