Abstract
We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to NL-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.
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., Martín-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)
Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inform. Comput. 97, 1–22 (1992)
García, P., Vázquez de Parga, M., López, D.: On the efficient construction of quasi-reversible automata for reversible languages. Inform. Process. Lett. 107, 13–17 (2008)
Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley (1978)
Héam, P.C.: A lower bound for reversible automata. RAIRO Inform. Théor. 34, 331–341 (2000)
Holzer, M., Jakobi, S.: Minimal and Hyper-Minimal Biautomata. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 291–302. Springer, Heidelberg (2014)
Immerman, N.: Nondeterministic space is closed under complement. SIAM J. Comput. 17, 935–938 (1988)
Kobayashi, S., Yokomori, T.: Learning approximately regular languages with reversible languages. Theoret. Comput. Sci. 174, 251–257 (1997)
Kutrib, M.: Aspects of Reversibility for Classical Automata. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 83–98. Springer, Heidelberg (2014)
Kutrib, M., Malcher, A.: Reversible Pushdown Automata. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 368–379. Springer, Heidelberg (2010)
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., Wendlandt, M.: Reversible queue automata. In: Non-Classical Models of Automata and Applications (NCMA 2014). books@ocg.at, vol. 304, pp. 163–178. Austrian Computer Society, Vienna (2014)
Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183–191 (1961)
Lombardy, S.: On the Construction of Reversible Automata for Reversible Languages. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 170–182. Springer, Heidelberg (2002)
Morita, K.: Two-way reversible multi-head finite automata. Fund. Inform. 110, 241–254 (2011)
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)
Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. Trans. IEICE E72, 223–228 (1989)
Pin, J.E.: On reversible automata. In: Latin 1992: Theoretical Informatics. LNCS, vol. 583, pp. 401–416. Springer (1992)
Ruzzo, W.L., Simon, J., Tompa, M.: Space-bounded hierarchies and probabilistic computations. J. Comput. System Sci. 28, 216–230 (1984)
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform. 26, 279–284 (1988)
Wagner, K., Wechsung, G.: Computational Complexity. Reidel (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Holzer, M., Jakobi, S., Kutrib, M. (2015). Minimal Reversible Deterministic Finite Automata. In: Potapov, I. (eds) Developments in Language Theory. DLT 2015. Lecture Notes in Computer Science(), vol 9168. Springer, Cham. https://doi.org/10.1007/978-3-319-21500-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-21500-6_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21499-3
Online ISBN: 978-3-319-21500-6
eBook Packages: Computer ScienceComputer Science (R0)