Abstract
Some aspects of logical reversibility for computing devices with a finite number of discrete internal states are addressed. These devices have a read-only input tape, may be equipped with further resources, and evolve in discrete time. The reversibility of a computation means in essence that every configuration has a unique successor configuration and a unique predecessor configuration. The notion of reversibility is discussed. In which way is the predecessor configuration computed? May we use a universal device? Do we have to use a device of the same type? Or else a device with the same computational power? Do we have to consider all possible configurations as potential predecessors? Or only configurations that are reachable from some initial configurations? We present some selected aspects as gradual reversibility and time-symmetry as well as results on the computational capacity and decidability mainly of finite automata and pushdown automata, and draw attention to the overall picture and some of the main ideas involved.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Angluin, D.: Inference of reversible languages. J. ACM 29, 741–765 (1982)
Axelsen, H.B.: Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 95–105. Springer, Heidelberg (2012)
Axelsen, H.B., Glück, R.: A simple and efficient universal reversible turing machine. In: Dediu, A.-H., Inenaga, S., Martin-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 117–128. Springer, Heidelberg (2011)
Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973)
Bordihn, H., Holzer, M., Kutrib, M.: Determinization of finite automata accepting subregular languages. Theoret. Comput. Sci. 410, 3209–3222 (2009)
Gajardo, A., Kari, J., Moreira, A.: On time-symmetry in cellular automata. J. Comput. System Sci. 78, 1115–1126 (2012)
García, P., Vázquez de Parga, M., Cano, A., López, D.: On locally reversible languages. Theoret. Comput. Sci. 410, 4961–4974 (2009)
Ginsburg, S., Greibach, S.A.: Deterministic context-free languages. Inform. Control 9, 620–648 (1966)
Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM 9, 350–371 (1962)
Ginzburg, A.: About some properties of definite, reverse-definite and related automata. IEEE Trans. Elect. Comput. EC–15, 806–810 (1966)
Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)
Havel, I.M.: The theory of regular events II. Kybernetica 6, 520–544 (1969)
Héam, P.C.: A lower bound for reversible automata. RAIRO Inform. Théor. 34, 331–341 (2000)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. AddisonWesley, Reading (1979)
Kari, J.: Reversible cellular automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 57–68. Springer, Heidelberg (2005)
Kobayashi, S., Yokomori, T.: Learning approximately regular languages with reversible languages. Theoret. Comput. Sci. 174, 251–257 (1997)
Kutrib, M., Malcher, A.: Fast reversible language recognition using cellular automata. Inform. Comput. 206, 1142–1151 (2008)
Kutrib, M., Malcher, A.: Real-time reversible iterative arrays. Theoret. Comput. Sci. 411, 812–822 (2010)
Kutrib, M., Malcher, A.: Reversible pushdown automata. J. Comput. System Sci. 78, 1814–1827 (2012)
Kutrib, M., Malcher, A.: One-Way reversible multi-head finite automata. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 14–28. Springer, Heidelberg (2013)
Kutrib, M., Malcher, A.: Real-time reversible one-way cellular automata. In: Cellular Automata and Discrete Complex Systems (AUTOMATA 2014) (to appear, 2014)
Kutrib, M., Malcher, A., Wendlandt, M.: Reversible Queue Automata. In: Non-Classical Models of Automata and Applications (NCMA 2014), vol. 304, pp. 163–178. Autralian Computer Society (2014)
Kutrib, M., Worsch, T.: Time-symmetric machines. In: Dueck, G.W., Miller, D.M. (eds.) RC 2013. LNCS, vol. 7948, pp. 168–181. Springer, Heidelberg (2013)
Kutrib, M., Worsch, T.: Degrees of Reversibility for DFA and DPDA. In: Yamashita, S., Minato, S. (eds.) RC 2014. LNCS, vol. 8507, pp. 40–53. Springer, Heidelberg (2014)
Lamb, J.S., Roberts, J.A.: Time-reversal symmetry in dynamical systems: A survey. Phys. D 112, 1–39 (1998)
Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183–191 (1961)
Lange, K.J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. J. Comput. System Sci. 60, 354–367 (2000)
McNaughton, R., Papert, S.: Counter-Free Automata. No. 65 in Research Monographs. MIT Press (1971)
Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148(1), 157–163 (1995)
Morita, K.: Reversible computing and cellular automata - a survey. Theoret. Comput. Sci. 395, 101–131 (2008)
Morita, K.: Two-way reversible multi-head finite automata. Fund. Inform. 110, 241–254 (2011)
Perles, M., Rabin, M.O., Shamir, E.: The theory of definite automata. IEEE Trans. Elect. Comput. EC–12, 233–243 (1963)
Pin, J.E.: On reversible automata. In: Simon, I. (ed.) Latin 1992. LNCS, vol. 583, pp. 401–416. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Kutrib, M. (2014). Aspects of Reversibility for Classical Automata. In: Calude, C., Freivalds, R., Kazuo, I. (eds) Computing with New Resources. Lecture Notes in Computer Science(), vol 8808. Springer, Cham. https://doi.org/10.1007/978-3-319-13350-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-13350-8_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13349-2
Online ISBN: 978-3-319-13350-8
eBook Packages: Computer ScienceComputer Science (R0)