dc.creator | Song, Bosheng | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Paun, Gheorghe | es |
dc.creator | Pan, Linqiang | es |
dc.date.accessioned | 2021-07-23T08:16:13Z | |
dc.date.available | 2021-07-23T08:16:13Z | |
dc.date.issued | 2016 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 1536-1241 | es |
dc.identifier.uri | https://hdl.handle.net/11441/116408 | |
dc.description.abstract | 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). | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2012-37434 | es |
dc.format | application/pdf | es |
dc.format.extent | 12 | es |
dc.language.iso | eng | es |
dc.publisher | IEEE Computer Society | es |
dc.relation.ispartof | IEEE Transactions on NanoBioscience, 15 (7), 645-656. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Bio-inspired computing | es |
dc.subject | Channel state | es |
dc.subject | Flat maximal parallelism | es |
dc.subject | Membrane Computing | es |
dc.subject | Tissue P Systems | es |
dc.subject | Tractability border | es |
dc.title | Tissue P Systems With Channel States Working in the Flat Maximally Parallel Way | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | TIN2012-37434 | es |
dc.relation.publisherversion | https://ieeexplore.ieee.org/abstract/document/7523387 | es |
dc.identifier.doi | 10.1109/TNB.2016.2594380 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
dc.journaltitle | IEEE Transactions on NanoBioscience | es |
dc.publication.volumen | 15 | es |
dc.publication.issue | 7 | es |
dc.publication.initialPage | 645 | es |
dc.publication.endPage | 656 | es |
dc.identifier.sisius | 21006837 | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | es |