Reversible Queue Automata

• Autorzy: Kutrib M. , Malcher A. , Wendlandt M.

Identyfikatory

DOI

10.3233/FI-2016-1438

• Języki publikacji: EN

Abstrakty

EN

Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue automaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of ...[formula] time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible.

Słowa kluczowe

EN

deterministic finite automata; computational complexity; formal languages; queuing theory; machine theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 341--368
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Kutrib M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Malcher A.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Wendlandt M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Angluin D. Inference of Reversible Languages, J. of ACM, 1982;29(3):741–765. doi:10.1145/322326.322334.
• [2] Bennett CH. Logical Reversibility of Computation, IBM J. Res. Dev., 1973;17(6):525–532. doi:10.1147/rd.176.0525.
• [3] Brandenburg FJ. Intersections of Some Families of Languages, International Colloquium on Automata, Languages and Programming (ICALP 1986) (L. Kott, Ed.), vol. 226 of LNCS, Springer, 1986, pp.60–68. Available from: http://dl.acm.org/citation.cfm?id=646240.683665.
• [4] Brandenburg FJ. On the Intersection of Stacks and Queues, Theoret. Comput. Sci., 1988;58(1-3):69–80. doi:10.1016/0304-3975(88)90019-9.
• [5] Cherubini A, Citrini C, Crespi-Reghizzi S., Mandrioli D. QRT FIFO Automata, Breadth-First Grammars and Their Relations, Theoret. Comput. Sci., 1991;85(1):171–203. doi:10.1016/0304-3975(91)90053-5.
• [6] Chomsky N. On Certain Formal Properties of Grammars, Inform. Control, 1959;2(2):137–167. doi: 10.1016/S0019-9958(59)90362-6.
• [7] Ginsburg, S., Greibach, S. A., Harrison, M. A.: One-Way Stack Automata, J. ACM, 14, 1967, 389–418.
• [8] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, 1979.
• [9] Jakobi S, Meckel K, Mereghetti C, Palano B. Queue Automata of Constant Length, Descriptional Complexity of Formal Systems (DCFS 2013) (H. Jürgensen, R. Reis, Eds.), vol 8031 of LNCS, Springer, 2013, pp. 125–135. doi:10.1007/978-3-642-39310-5_13.
• [10] Kutrib M, Malcher A. Fast Reversible Language Recognition Using Cellular Automata, Inform. Comput., 2008;206(9-10):1142–1151. doi:10.1016/j.ic.2008.03.015.
• [11] Kutrib M, Malcher A. Reversible Pushdown Automata, J. Comput. System Sci., 2012;78(6):1814–1827. Available from: http://dx.doi.org/10.1016/j.jcss.2011.12.004.
• [12] Kutrib M, Malcher A. One-Way Reversible Multi-head Finite Automata, Reversible Computation (RC 2012), (R. Glück, T. Yokoyama, Eds.), vol. 7581 of LNCS, Springer, 2013. doi:10.1007/978-3-642-36315-3.
• [13] Kutrib M, Malcher A, Mereghetti C, Palano B, Wendlandt M. Deterministic input-driven queue automata: Finite turns, decidability, and closure properties. Theor. Comput. Sci., 2015;578(C):58–71. doi:10.1016/j.tcs.2015.01.012.
• [14] Landauer R. Irreversibility and Heat Generation in the Computing Process, IBM J. Res. Dev., 1961;5(3):183–191. doi:10.1147/rd.53.0183.
• [15] Lange KJ, McKenzie P, Tapp A. Reversible Space Equals Deterministic Space, J. Comput. System Sci., 2000;60(2):354–367. doi:10.1006/jcss.1999.1672.
• [16] Li M, Vitányi PMB. An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1993. ISBN: 978-1-4757-3862-9, 978-1-4757-3860-5.
• [17] Morita K. Reversible Computing and Cellular Automata – A survey, Theoret. Comput. Sci., 2008; 395(1):101–131. doi:10.1016/j.tcs.2008.01.041.
• [18] Morita K. Two-Way Reversible Multi-Head Finite Automata, Fund. Inform., 2011;110:241–254. Available from: http://fi.mimuw.edu.pl/index.php/FIhttp://content.iospress.com/journals/fundamenta-informaticae/145/2 doi:10.3233/FI-2011-541.
• [19] Pin JE. On Reversible Automata, Latin 1992: Theoretical Informatics, vol. 583 of LNCS, Springer, 1992, pp.401–416. ISBN: 3-540-55284-7.
• [20] Vollmar R. Über einen Automaten mit Pufferspeicherung, Computing, 1970;5(1):57–70. doi:10.1007/BF02234250.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).