Two-Way Reversible Multi-Head Finite Automata

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Morita, Kenichi

Affiliations: Department of Information Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan. morita@iec.hiroshima-u.ac.jp

Note: [] Address for correspondence: Dept. of Information Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

Abstract: 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.

Keywords: reversible computing, multi-head finite automaton, language recognition

DOI: 10.3233/FI-2011-541

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 241-254, 2011