On String Languages Generated by Sequential Numerical P Systems

• Autorzy: Zhang Z. , Wu T. , Pan L.

Identyfikatory

DOI

10.3233/FI-2016-1372

• Języki publikacji: EN

Abstrakty

EN

Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics. In this work, we further investigate the generative capacity of numerical P systems as language generators. The families of languages generated by non-enzymatic, by enzymatic, and by purely enzymatic (all programs are enzymatic) numerical P systems working in the sequential mode are compared with the language families in the Chomsky hierarchy. Especially, a characterization of recursively enumerable languages is obtained by using purely enzymatic numerical P systems working in the sequential mode.

Słowa kluczowe

EN

computational power; formal language; numerical p system; register machine; sequential; string language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 4
• Strony: 485--509
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Zhang Z.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Wu T.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Pan L.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

Bibliografia

• [1] Chen H, Ishdorj TO, Pǎun G, Pérez-Jiménez MJ. Spiking neural P systems with extended rules, Proc. Fourth Brainstorming Week on Membrane Computing, RGNC Report, Sevilla, 2006; p. 241–265.
• [2] Chen H, Rudolf F, Ionescu M, Pǎun G, Pérez-Jiménez MJ. On string languages generated by spiking neural P systems, Fundamenta Informaticae, 2007;75(1-4):141–162. ISSN:0169-2968, 1875-8681.
• [3] Ionescu M, Pǎun G, Yokomori T. Spiking neural P systems, Fundamenta Informaticae, 71(2-3), 2006, 279–308. ISSN:0169-2968, 1875-8681.
• [4] Leporati A, Porreca AE, Zandron C, Mauri G. Improved universality results for parallel enzymatic numerical P systems. International Journal of Unconventional Computing, 9(5), 2013, 385–404.
• [5] Minsky ML. Computation: Finite and Infinite Machines, Prentice-Hall, Inc., New Jork 1967. ISBN:0-13-165563-9.
• [6] Pǎun G. Membrane Computing – An Introduction, Springer-Verlag, Berlin, 2002. doi:10.1007/978-3-642-56196-2.
• [7] Pǎun G, Pǎun R. Membrane computing and economics: Numerical P systems, Fundamenta Informaticae, 2006;73(1):213–227. ISSN:0169-2968, 1875-8681.
• [8] Pǎun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010. ISBN:0199556679, 9780199556670.
• [9] Pavel AB, Arsene O, Buiu C. Enzymatic numerical P systems – A new class of membrane computing systems, Proc. IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications, 2010, p.1331–1336. 10.1109/BICTA.2010.5645071.
• [10] Pavel AB, Buiu C. Using enzymatic numerical P systems for modeling mobile robot controllers, Natural Computing, 2012; 3(11):387–393. doi:10.1007/s11047-011-9286-5.
• [11] Pavel AB, Vasile CI, Dumitrache I. Robot localization implemented with enzymatic numerical P systems, Proceedings of Living Machines 2012, Springer-Verlag, Barcelona, Spain, July 2012, LNAI 7375, p.204–215. doi:10.1007/978-3-642-31525-1 18.
• [12] Pavel AB, Vasile CI, Dumitrache I. Membrane Computing in Robotics, vol. 4 of Topics in Intelligent Engineering and Informatics, chapter Beyond Artificial Intelligence, Springer Berlin Heidelberg, 2013;4:125–135. doi:10.1007/978-3-642-34422-0 9.
• [13] Rozenberg G, Salomaa A. Handbook of Formal Languages, vol. 1–3, Springer Science & Business Media, Berlin, 1997.
• [14] Vasile CI, Pavel AB, Dumitrache I. Universality of enzymatic numerical P systems, International Journal of Computer Mathematics, 2013;90(4):869–879. doi:10.1080/00207160.2012.748897.
• [15] Vasile CI, Pavel AB, Dumitrache I, Pǎun G. On the power of enzymatic numerical P systems, Acta Informatica, 2012;49(6):395-412. doi:10.1007/s00236-012-0166-y.
• [16] Zhang Z. Enzymatic Numerical P Systems Working in the Sequential Mode, to be submitted, 2016.
• [17] Zhang Z, Pan L. Numerical P systems with thresholds, International Journal of Computers Communications & Control, 11(2), 2016, 292–304. doi:10.15837/ijccc.2016.2.2262.
• [18] Zhang Z, Wu T, Pan L, Pǎun G. On String Languages Generated by Numerical P Systems, submitted to Romanian Journal of Information Science and Technology, 2015.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).