P systems with minimal parallelism

@article{citeulike:2366446, abstract = {A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time).}, author = {Ciobanu, Gabriel and Pan, Linqiang and Paun, Gheorghe and Perez-Jimenez, Mario J. }, citeulike-article-id = {2366446}, doi = {10.1016/j.tcs.2007.03.044}, journal = {Theoretical Computer Science}, keywords = {complexity, minimal, mythesis, parallelism, p-systems}, month = {June}, number = {1}, pages = {117--130}, posted-at = {2008-02-12 16:07:11}, priority = {2}, title = {P systems with minimal parallelism}, url = {http://dx.doi.org/10.1016/j.tcs.2007.03.044}, volume = {378}, year = {2007} }

TY - JOUR ID - citeulike:2366446 L3 - citeulike-article-id:2366446 TI - P systems with minimal parallelism JF - Theoretical Computer Science VL - 378 IS - 1 SP - 117 EP - 130 N2 - A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time). KW - complexity KW - minimal KW - mythesis KW - parallelism KW - p-systems AU - Ciobanu, Gabriel AU - Pan, Linqiang AU - Paun, Gheorghe AU - Perez-Jimenez, Mario PY - 2007/06/03/ UR - http://dx.doi.org/10.1016/j.tcs.2007.03.044 ER -