title: Tissue P Systems With Channel States Working in the Flat Maximally Parallel Way.
abstract: Tissue 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 ).
authors.forename: Bosheng
authors.initials: B
authors.lastname: Song
authors.forename: Mario J
authors.initials: MJ
authors.lastname: Perez-Jimenez
authors.forename: Gheorghe
authors.initials: G
authors.lastname: Paun
authors.forename: Linqiang
authors.initials: L
authors.lastname: Pan
mesh_terms: D002455:Cell Division; D002462:Cell Membrane / Q000737:chemistry / Q000378:metabolism; D003198:Computer Simulation; D039301:Computers, Molecular; D008954:Models, Biological