Affiliations: Faculty of Arts and Science, Kyushu University, Center Zone, Ito Campus, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan. fokubo@artsci.kyushu-u.ac.jp | Department of Mathematics, Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan. yokomori@waseda.jp
Note: [] The work of F. Okubo was in part supported by Grants-in-Aid for JSPS Fellows No.25.3528, Japan Society for the Promotion of Science.
Note: [] The work of T. Yokomori was in part supported by a Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No. 24104003) of The Ministry of Education, Culture, Sports, Science, and Technology, Japan, and Waseda University grant for Special Research Projects: 2013B-063 and 2013C-159. Address for correspondence: Department of Mathematics, Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan
Abstract: This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-bounded FAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy.
Keywords: finite automata, multiset memory, computation power, Chomsky hierarchy of languages
