Two-Way Reversible Multi-Head Finite Automata

• Autorzy: Morita K.
• Języki publikacji: EN

Abstrakty

EN

A two-way reversible multi-head finite automaton (RMFA) is introduced as a simple model of reversible computing, and its language accepting capability is studied. We show that various non-regular context-free languages, and non-context-free context-sensitive languages are accepted by RMFAs with a few heads. For example, we give an RMFA with three heads that accepts the language consisting of all words whose length is a prime number. A construction method of a garbage-less RMFA from a given RFMA is also shown.

Słowa kluczowe

EN

reversible computing; multi-head finite automaton; language recognition

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 241--254
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Morita K.

• Department of Information Engineering, Hiroshima University Higashi-Hiroshima, 739-8527, Japan,

Bibliografia

• [1] Bennett, C. H.: Logical reversibility of computation, IBM J. Res. Dev., 17, 1973, 525-532.
• [2] Fredkin, E., Toffoli, T.: Conservative logic, Int. J. Theoret. Phys., 21, 1982, 219-253.
• [3] Holzer, M., Kutrib, M., Malcher, A.: Complexity of multi-head finite automata: Origins and directions, Theoret. Comput. Sci., 412, 2011, 83-96.
• [4] Ibarra, O.: On two-way multihead automata, J. Comput. Syst. Sci., 7, 1973, 28-36.
• [5] Kutrib, M., Malcher, A.: Reversible pushdown automata, Proc. LATA 2010, LNCS 6031, Springer-Verlag, 2010, 368-379.
• [6] Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space, J. Comput. Syst. Sci., 60, 2000, 354-367.
• [7] Lecerf, Y.: Machines de Turing réversibles - récursive insolubilité en n ∈ N de l'équation u = _nu, o`u _ est un isomorphisme de codes, Comptes Rendus Hebdomadaires des Séances de L'académie des Sciences, 257, 1963, 2597-2600.
• [8] Monien, B.: Transformational methods and their application to complexity theory, Acta Inform., 6, 1976, 95-108.
• [9] Morita, K.: Universality of a reversible two-counter machine, Theoret. Comput. Sci., 168, 1996, 303-320.
• [10] Morita, K.: Reversible computing and cellular automata - A survey, Theoret. Comput. Sci., 395, 2008, 101-131.
• [11] Morita, K.: Constructing a reversible Turing machine by a rotary element, a reversible logic element with memory, Hiroshima University Institutional Repository, http://ir.lib.hiroshima-u.ac.jp/00029224, 2010.
• [12] Rabin, M., Scott, D.: Finite automata and their decision problems, IBM J. Res. Dev., 3, 1959, 114-125.
• [13] Rosenberg, A.: On multi-head finite automata, IBM J. Res. Dev., 10, 1966, 388-394.
• [14] Toffoli, T.: Computation and construction universality of reversible cellular automata, J. Comput. Syst. Sci., 15, 1977, 213-231.
• [15] Toffoli, T.: Reversible computing, Automata, Languages and Programming, LNCS 85, Springer-Verlag, 1980, 632-644.