Song, BoshengPérez Jiménez, Mario de JesúsPaun, GheorghePan, Linqiang2021-07-232021-07-232016Song, 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.1536-1241https://hdl.handle.net/11441/116408issue 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).application/pdf12engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Bio-inspired computingChannel stateFlat maximal parallelismMembrane ComputingTissue P SystemsTractability borderinfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccesshttps://doi.org/10.1109/TNB.2016.2594380