Abstract
The paper proposes a general notation for deterministic automata traversing finite undirected structures: the graph-walking automata. This abstract notion covers such models as two-way finite automata, including their multi-tape and multi-head variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. It is then demonstrated that every graph-walking automaton can be transformed to an equivalent reversible graph-walking automaton, so that every step of its computation is logically reversible. This is done with a linear blow-up in the number of states, where the linear factor depends on the degree of graphs being traversed. The construction directly applies to all basic models covered by this abstract notion.
Supported by ESF project CZ.1.07/2.3.00/20.0051 “Algebraic Methods in Quantum Logic”, and by Academy of Finland project 257857.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abramsky, S.: A structural approach to reversible computation. Theoretical Computer Science 347(3), 441–464 (2005)
Aho, A.V., Ullman, J.D.: Translations on a context free grammar. Information and Control 19(5), 439–475 (1971)
Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development 17(6), 525–532 (1973)
Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM Journal on Computing 81, 766–776 (1989)
Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: SWAT 1967, pp. 155–160 (1967)
Bojańczyk, M., Colcombet, T.: Tree-walking automata cannot be determinized. Theoretical Computer Science 350(2-3), 164–173 (2006)
Bojańczyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM Journal on Computing 38(2), 658–701 (2008)
Buhrman, H., Tromp, J., Vitányi, P.: Time and space bounds for reversible simulation. Journal of Physics A: Mathematical and General 34(35), 6821–6830 (2001)
Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol. B, pp. 193–242 (1990)
Crescenzi, P., Papadimitriou, C.H.: Reversible simulation of space-bounded computations. Theoretical Computer Science 143(1), 159–165 (1995)
Engelfriet, J., Hoogeboom, H.J.: Tree-walking pebble automata. Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, 72–83 (1999)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoretical Computer Science 345(2-3), 331–344 (2005)
Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation 205(8), 1173–1187 (2007)
Hopcroft, J.E., Ullman, J.D.: Some results on tape bounded Turing machines. Journal of the ACM 16, 168–177 (1967)
Kari, J.: Reversible cellular automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 57–68. Springer, Heidelberg (2005)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997, pp. 66–75 (1997)
Kutrib, M., Malcher, A.: Reversible pushdown automata. Journal of Computer and System Sciences 78(6), 1814–1827 (2012)
Landauer, R.: Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5(3), 183–191 (1961)
Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. Journal of Computer and System Sciences 60(2), 354–367 (2000)
Lecerf, Y.: Machines de Turing réversibles. Comptes Rendus de l’Académie des Sciences 257, 2597–2600 (1963)
Morita, K.: A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 29–43. Springer, Heidelberg (2013)
Muscholl, A., Samuelides, M., Segoufin, L.: Complementing deterministic tree-walking automata. Information Processing Letters 99(1), 33–39 (2006)
Pin, J.-É.: On the languages accepted by finite reversible automata. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol. 267, pp. 237–249. Springer, Heidelberg (1987)
Sipser, M.: Halting space-bounded computations. Theoretical Computer Science 10(3), 335–338 (1980)
Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodríguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 441–454. Springer, Heidelberg (1991)
Toffoli, T., Margolus, N.H.: Invertible cellular automata: A review. Physica D: Nonlinear Phenomena 45(1-3), 229–253 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kunc, M., Okhotin, A. (2013). Reversibility of Computations in Graph-Walking Automata. In: Chatterjee, K., Sgall, J. (eds) Mathematical Foundations of Computer Science 2013. MFCS 2013. Lecture Notes in Computer Science, vol 8087. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40313-2_53
Download citation
DOI: https://doi.org/10.1007/978-3-642-40313-2_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40312-5
Online ISBN: 978-3-642-40313-2
eBook Packages: Computer ScienceComputer Science (R0)