No Access

Weakly and Strongly Irreversible Regular Languages

Bruno Guillon

LIMOS, Université Clermont-Auvergne, France

E-mail Address: bruno.guillon@uca.fr

Corresponding author.

Search for more papers by this author

Giovanna J. Lavado

Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy

E-mail Address: lavado@di.unimi.it

Search for more papers by this author

Giovanni Pighizzini

Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy

E-mail Address: pighizzini@di.unimi.it

Corresponding author.

Search for more papers by this author

, and

Luca Prigioniero

Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy

E-mail Address: prigioniero@di.unimi.it

Search for more papers by this author

https://doi.org/10.1142/S0129054122410052Cited by:0 (Source: Crossref)

This article is part of the issue:

Special Issue: 15th International Conference on Automata and Formal Languages

Abstract

Finite automata whose computations can be reversed, at any point, by knowing the last $k$ $k$ symbols read from the input, for a fixed $k$ $k$ , are considered. These devices and their accepted languages are called $k$ $k$ -reversible automata and $k$ $k$ -reversible languages, respectively. The existence of $k$ $k$ -reversible languages which are not $(k - 1)$ $(k - 1)$ -reversible is known, for each $k > 1$ $k > 1$ . This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are $k$ $k$ -reversible for some $k$ $k$ . Conditions characterizing the class of $k$ $k$ -reversible languages, for each fixed $k$ $k$ , and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not $k$ $k$ -reversible, but which accepts a $k$ $k$ -reversible language, into an equivalent $k$ $k$ -reversible finite automaton, is presented.

Communicated by Erzsébet Csuhaj-Varjú, Pál Dömösi, and György Vaszil

Keywords:

References

1. D. Angluin, Inference of reversible languages, J. ACM 29(3) (1982) 741–765. Crossref, Web of Science, Google Scholar
2. C. H. Bennett, Logical reversibility of computation, IBM Journal of Research and Development 17(6) (1973) 525–532. Crossref, Web of Science, Google Scholar
3. M. Holzer, S. Jakobi and M. Kutrib, Minimal reversible deterministic finite automata, International Journal of Foundations of Computer Science 29(2) (2018) 251–270. Link, Web of Science, Google Scholar
4. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, 1979). Google Scholar
5. N. D. Jones, Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences 11(1) (1975) 68–85. Crossref, Web of Science, Google Scholar
6. A. Kondacs and J. Watrous, On the power of quantum finite state automata, FOCS (IEEE Computer Society, 1997), pp. 66–75. Crossref, Google Scholar
7. M. Kutrib, Reversible and irreversible computations of deterministic finite-state devices, Mathematical Foundations of Computer Science 2015 — 40th International Symposium, MFCS 2015, Milan, Italy, August 24–28, 2015, Proceedings, Part I, eds. G. F. Italiano, G. Pighizzini and D. Sannella, Lecture Notes in Computer Science, Vol. 9234 (Springer, 2015), pp. 38–52. Crossref, Google Scholar
8. M. Kutrib and T. Worsch, Degrees of reversibility for DFA and DPDA, Reversible Computation — 6th International Conference, RC 2014, Kyoto, Japan, July 10–11, 2014. Proceedings, eds. S. Yamashita and S. Minato, Lecture Notes in Computer Science, Vol. 8507 (Springer, 2014), pp. 40–53. Crossref, Google Scholar
9. R. W. Landauer, Irreversibility and heat generation in the computing process, IBM Journal of Research and Development 5 (1961) 183–191. Crossref, Web of Science, Google Scholar
10. K. Lange, P. McKenzie and A. Tapp, Reversible space equals deterministic space, Journal of Computer and System Science 60(2) (2000) 354–367. Crossref, Web of Science, Google Scholar
11. G. J. Lavado, G. Pighizzini and L. Prigioniero, Minimal and reduced reversible automata, Journal of Automata, Languages and Combinatorics 22(1–3) (2017) 145–168. Google Scholar
12. G. J. Lavado and L. Prigioniero, Concise representations of reversible automata, International Journal of Foundations of Computer Science 30(6–7) (2019) 1157–1175. Link, Web of Science, Google Scholar
13. S. Lombardy, On the construction of reversible automata for reversible languages, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8–13, 2002, Proceedings, eds. P. Widmayer, F. T. Ruiz, R. M. Bueno, M. Hennessy, S. Eidenbenz and R. Conejo, Lecture Notes in Computer Science, Vol. 2380 (Springer, 2002), pp. 170–182. Crossref, Google Scholar
14. G. Pighizzini, Investigations on automata and languages over a unary alphabet, International Journal of Foundations of Computer Science 26(7) (2015) 827–850. Link, Web of Science, Google Scholar
15. J. Pin, On reversible automata, LATIN ’92, 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6–10, 1992, Proceedings, ed. I. Simon, Lecture Notes in Computer Science, Vol. 583 (Springer, 1992), pp. 401–416. Crossref, Google Scholar