Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2019.06.021 | Theoretical Computer Science |
Keywords | Field | DocType |
Finite state transducers,Reversible computations,Computational capacity,Closure properties,Gradual reversibility | Topology,Computer science,Finite-state machine,Computation | Conference |
Volume | ISSN | Citations |
787 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutrib | 1 | 778 | 89.77 |
| Andreas Malcher | 2 | 204 | 39.40 |
| Matthias Wendlandt | 3 | 32 | 14.13 |