Finite Automata with Multiset Memory : A New Characterization of Chomsky Hierarchy

• Autorzy: Okubo F. , Yokomori T.

Identyfikatory

DOI

10.3233/FI-2015-1196

• Języki publikacji: EN

Abstrakty

EN

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-boundedFAMMs 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.

Słowa kluczowe

EN

finite automata; multiset memory; computation power; Chomsky hierarchy of languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 331--44
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Okubo F.

• Faculty of Arts and Science, Kyushu University Center Zone, Ito Campus, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan

autor

Yokomori T.

• Department of Mathematics, Faculty of Education and Integrated Arts and Sciences Waseda University 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan

Bibliografia

• [1] Alhazov,A. and Rogozhin,Y.: One-membrane symport with few extra symbols, International Journal of Computer Mathematics vol.90,No.4, pp.750-759, 2013.
• [2] Alhazov,A. and Verlan,S.: Minimization strategies for maximally parallel multiset rewriting systems, Theoretical Computer Science, vol.412, pp.1587-1591, 2011.
• [3] Angluin, D., Aspnes, J., and Eisenstat, D.: Stably computable predicates are semilinear, in Proceedings of the 25th annual ACM symposium on principles of distributed computing, ACM Press, New York, pp.292-299. 2006.
• [4] Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., and Peralta, R.: Urn automata, Technical Report YALEU/DCS/TR-1280, Yale University, Department of Computer Cience (2003).
• [5] Calude, C., Păun,Gh., Rozenberg,G., and Salomaa,A. (Eds.): Multiset Processing, Lect. Notes Comput. Sci. vol.2235, Springer, 2001.
• [6] Csuhaj-Varju,E.,Martin-Vide,C., and Mitrana,V.: Multiset Automata, in: Multiset Processing, C. Calude, Gh. Păun, G. Rozenberg, A. Salomaa (Eds.), Lect. Notes Comput. Sci. vol.2235, Springer, pp.69-83, 2001.
• [7] Csuhaj-Varju,E. and Vaszil,Gv.: P automata, in The Oxford Handbook of Membrane Computing, pp.145-167, 2010.
• [8] Fischer,P.C., Meyer,A.R. and Rozenberg,A.L.: Counter Machines and Counter Languages, Mathematical Systems Theory, vol.2 (3), pp.265-283, 1968.
• [9] Hirshfeld,Y.,Moller,F.: Pushdown automata, multiset automata, and Petri nets, Theoretical Computer Science, vol.256, pp.3-21, 2001.
• [10] Hopcroft,J.E., Motwani,T., and Ullman,J.D.: Introduction to automata theory, language and computation -3rd ed, Addison-Wesley, 2007.
• [11] Ibarra, O.H., Păun, Gh.: Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems, Theoretical Computer Science, vol.358, pp.88-103, 2006.
• [12] Kudlek,M., Totzke,P., and Zetzsche,G.: Multiset pushdown automata, Fundamenta Informaticae, vol.93, pp.221-233, 2009.
• [13] Okubo, F.: Reaction automata working in sequential manner, RAIRO Theoretical Informatics and Applications, vol.48, pp.23-38, 2014.
• [14] Okubo, F., Kobayashi,S., and Yokomori, T.: Reaction automata, Theoretical Computer Science, vol.429, pp.247-257, 2012.
• [15] Okubo, F., Kobayashi,S., and Yokomori, T.: On the properties of language classes defined by bounded reaction automata, Theoretical Computer Science, vol.454, pp.206-221, 2012.
• [16] Okubo, F. and Yokomori, T.: Recent developments on reaction automata theory: A survey, Proc. of 7th International Workshop on Natural Computing, Springer Japan, in press, 2014.
• [17] Okubo, F. and Yokomori, T.: The computational power of chemical reaction automata, Proc. 20th International Conference on DNA Computing and Molecular Programming, Kyoto, LNCS 8727, pp.53-66, 2014.
• [18] Vaszil, Gy.: A Class of P Automata for Characterizing Context-Free Languages, Proc. Fourth Brainstorming Week on Membrane Computing, Sevilla, vol. II (C. Graciani et al., eds.), pp.267-276, 2006.