caa a22 4500 605470847 CHVBK 20210128100330.0 cr unu---uuuuu 210128e20151101xx s 000 0 eng 10.1007/s00500-015-1732-3 doi (NATIONALLICENCE)springer-10.1007/s00500-015-1732-3 Computational efficiency and universality of timed P systems with membrane creation [Elektronische Daten] [Bosheng Song, Mario Pérez-Jiménez, Linqiang Pan] P systems are a class of distributed parallel computing models inspired by the structure and the functioning of a living cell, where the execution of each rule is completed in exactly one time unit (a global clock is assumed). However, in living cells, the execution time of different biological processes is difficult to know precisely and very sensitive to environmental factors that might be hard to control. Inspired from this biological motivation, in this work, timed polarization P systems with membrane creation are introduced and their computational efficiency and universality are investigated. Specifically, we give a time-free semi-uniform solution to the SAT problem by a family of P systems with membrane creation in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules. We also prove that time-free P systems with membrane creation are computationally universal. Springer-Verlag Berlin Heidelberg, 2015 P system nationallicence Membrane creation nationallicence Time-free solution nationallicence SAT problem nationallicence Universality nationallicence Song Bosheng Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, 430074, Wuhan, Hubei, China aut Pérez-Jiménez Mario Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain aut Pan Linqiang Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, 430074, Wuhan, Hubei, China aut Soft Computing Springer Berlin Heidelberg 19/11(2015-11-01), 3043-3053 1432-7643 19:11<3043 2015 19 500 https://doi.org/10.1007/s00500-015-1732-3 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00500-015-1732-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Song Bosheng Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, 430074, Wuhan, Hubei, China aut NATIONALLICENCE 700 1- Pérez-Jiménez Mario Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain aut NATIONALLICENCE 700 1- Pan Linqiang Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, 430074, Wuhan, Hubei, China aut NATIONALLICENCE 773 0- Soft Computing Springer Berlin Heidelberg 19/11(2015-11-01), 3043-3053 1432-7643 19:11<3043 2015 19 500