Reversible Limited Automata

• Autorzy: Kutrib M. , Wendlandt M.

Identyfikatory

DOI

10.3233/FI-2017-1575

• Języki publikacji: EN

Abstrakty

EN

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all k≥ 0, sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and k + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k-limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

Słowa kluczowe

EN

machine theory; reversible computing; finite state machine; statistical matching; homomorphisms; cellular automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 31--58
• Opis fizyczny: Bibliogr. 31 poz., rys.

Twórcy

autor

Kutrib M.

• 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] Hennie FC. One-Tape, Off-Line Turing Machine Computations. Inform Control. 1965;8(6):553–578. URL https://doi.org/10.1016/S0019-9958(65)90399-2.
• [2] Hartmanis J. Computational Complexity of One-Tape Turing Machine Computations. J ACM. 1968;15(2):325–339. doi:10.1145/321450.321464.
• [3] Průša D. Weight-Reducing Hennie Machines and Their Descriptional Complexity. In: Language and Automata Theory and Applications (LATA 2014). vol. 8370 of LNCS. Springer; 2014. p. 553–564. doi:10.1007/978-3-319-04921-2_45.
• [4] Hibbard TN. A Generalization of Context-Free Determinism. Inform Control. 1967;11:196–238.
• [5] Pighizzini G, Pisoni A. Limited Automata and Regular Languages. Int J Found Comput Sci. 2014;25:897–916. URL http://dx.doi.org/10.1142/S0129054114400140.
• [6] Pighizzini G, Pisoni A. Limited Automata and Context-Free Languages. Fund Inform. 2015;136(1-2):157–176. doi:10.3233/FI-2015-1148.
• [7] Kutrib M, Wendlandt M. On Simulation Costs of Unary Limited Automata. In: Descriptional Complexity of Formal Systems (DCFS 2015). vol. 9118 of LNCS. Springer; 2015. p. 153–164. doi:10.1007/978-3-319-19225-3_13.
• [8] Bennett CH. Logical reversibility of Computation. IBM J Res Dev. 1973;17(6):525–532. doi:10.1147/rd.176.0525.
• [9] Landauer R. Irreversibility and heat generation in the computing process. IBM J Res Dev. 1961;5:183–191.
• [10] Angluin D. Inference of reversible languages. J ACM. 1982;29(3):741–765. doi:10.1145/322326.322334.
• [11] Holzer M, Jakobi S, Kutrib M. Minimal Reversible Deterministic Finite Automata. In: Developments in Language Theory (DLT 2015). vol. 9168 of LNCS. Springer; 2015. p. 276–287. doi:10.1007/978-3-319-21500-6_22.
• [12] Kondacs A, Watrous J. On the Power of Quantum Finite State Automata. In: Foundations of Computer Science (FOCS 1997). IEEE Computer Society; 1997. p. 66–75. doi:10.1109/SFCS.1997.646094.
• [13] Kutrib M,Worsch T. Degrees of Reversibility for DFA and DPDA. In: Reversible Computation (RC 2014). vol. 8507 of LNCS. Springer; 2014. p. 40–53. doi:10.1007/978-3-319-08494-7_4.
• [14] Pin JE. On reversible automata. In: Latin 1992: Theoretical Informatics. vol. 583 of LNCS. Springer; 1992. p. 401–416. doi:10.1007/BFb0023844.
• [15] Kutrib M, Malcher A. Reversible Pushdown Automata. J Comput System Sci. 2012;78(6):1814–1827. doi:10.1016/j.jcss.2011.12.004.
• [16] Lange KJ, McKenzie P, Tapp A. Reversible Space Equals Deterministic Space. J Comput System Sci. 2000;60(2):354–367. URL https://doi.org/10.1006/jcss.1999.1672.
• [17] Axelsen HB. Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space. In: Language and Automata Theory and Applications (LATA 2012). vol. 7183 of LNCS. Springer; 2012. p. 95–105. doi:10.1007/978-3-642-28332-1_9.
• [18] Kutrib M, Malcher A. One-Way Reversible Multi-head Finite Automata. In: Reversible Computation (RC 2012). vol. 7581 of LNCS. Springer; 2013. p. 14–28.
• [19] Morita K. Two-Way Reversible Multi-Head Finite Automata. Fund Inform. 2011;110(1-4):241–254. doi:10.3233/FI-2011-541.
• [20] Morita K. A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads. In: Reversible Computation (RC 2012). vol. 7581 of LNCS. Springer; 2013. p. 29–43. doi:10.1007/978-3-642-36315-3_3.
• [21] Kutrib M, Malcher A, Wendlandt M. Reversible Queue Automata. In: Non-Classical Models of Automata and Applications (NCMA 2014). vol. 304 of [e-mail]. Austrian Computer Society; 2014. p. 163–178. URL https://db/conf/ncma/ncma2014.html#KutribMW14.
• [22] Kutrib M, Malcher A. Fast reversible language recognition using cellular automata. Inform Comput. 2008;206(9-10):1142–1151. URL https://doi.org/10.1016/j.ic.2008.03.015.
• [23] Morita K. Reversible computing and cellular automata–A survey. Theoret Comput Sci. 2008;395(1):101–131. URL https://doi.org/10.1016/j.tcs.2008.01.041.
• [24] Kutrib M. Aspects of Reversibility for Classical Automata. In: Computing with New Resources. vol. 8808 of LNCS. Springer; 2014. p. 83–98. doi:10.1007/978-3-319-13350-8_7.
• [25] Geffert V, Mereghetti C, Pighizzini G. Complementing two-way finite automata. Inform Comput. 2007;205(8):1173–1187. URL https://doi.org/10.1016/j.ic.2007.01.008.
• [26] Sipser M. Halting Space-Bounded Computations. Theoret Comput Sci. 1980;10:335–338. doi:10.1016/0304-3975(80)90053-5.
• [27] McNaughton R, Narendran P, Otto F. Church-Rosser Thue Systems and Formal Languages. J ACM. 1988;35(2):324–344. doi:10.1145/42282.42284.
• [28] Buntrock G, Otto F. Growing Context-Sensitive Languages and Church-Rosser Languages. Inform Comput. 1998;141(1):1–36. doi:10.1006/inco.1997.2681.
• [29] Kutrib M, Malcher A. When Church-Rosser Becomes Context Free. Int J Found Comput Sci. 2007;18:1293–1302. doi:10.1142/S0129054107005339.
• [30] Niemann G, Otto F. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform Comput. 2005;197(1-2):1–21. doi:10.1016/j.ic.2004.09.003.
• [31] Kutrib M, Messerschmidt H, Otto F. On Stateless Two-Pushdown Automata and Restarting Automata. Int J Found Comput Sci. 2010;21(5):781–798. URL http://dx.doi.org/10.1142/S0129054110007556.