Artículo
Tissue P Systems With Channel States Working in the Flat Maximally Parallel Way
Autor/es | Song, Bosheng
Pérez Jiménez, Mario de Jesús Paun, Gheorghe Pan, Linqiang |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2016 |
Fecha de depósito | 2021-07-23 |
Publicado en |
|
Resumen | issue P systems with channel states are a class of bio-inspired parallel computational models, where rules are used in a sequential manner (on each channel, at most one rule can be used at each step). In this work, tissue ... issue P systems with channel states are a class of bio-inspired parallel computational models, where rules are used in a sequential manner (on each channel, at most one rule can be used at each step). In this work, tissue P systems with channel states working in a flat maximally parallel way are considered, where at each step, on each channel, a maximal set of applicable rules that pass from a given state to a unique next state, is chosen and each rule in the set is applied once. The computational power of such P systems is investigated. Specifically, it is proved that tissue P systems with channel states and antiport rules of length two are able to compute Parikh sets of finite languages, and such P systems with one cell and noncooperative symport rules can compute at least all Parikh sets of matrix languages. Some Turing universality results are also provided. Moreover, the NP-complete problem SAT is solved by tissue P systems with channel states, cell division and noncooperative symport rules working in the flat maximally parallel way; nevertheless, if channel states are not used, then such P systems working in the flat maximally parallel way can solve only tractable problems. These results show that channel states provide a frontier of tractability between efficiency and non-efficiency in the framework of tissue P systems with cell division (assuming P ≠ NP). |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | TIN2012-37434 |
Cita | Song, B., Pérez Jiménez, M.d.J., Paun, G. y Pan, L. (2016). Tissue P Systems With Channel States Working in the Flat Maximally Parallel Way. IEEE Transactions on NanoBioscience, 15 (7), 645-656. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Tissue P systems with channel ... | 1.172Mb | [PDF] | Ver/ | |