Parallelism and Synchronization in P Systems and Related Models
Membrane computing identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. Due to the built-in nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively parallel systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology (or silicon-technology) gives way to a practical bio-realization (or chip-realization) . In the standard semantics of P systems, each evolution step of a system P is a result of applying all the rules in P in a maximally parallel manner. More precisely, starting from the initial configuration, the system goes through a sequence of configurations, where each configuration is derived from the directly preceding configuration in one step by the application of a multiset of rules, which are chosen nondeterministically. We require that the application of the rules is maximal: all objects, from all membranes, which can be the subject of local evolution rules have to evolve simultaneously. Thus, in general, the number of tirues a particular rule is applied at any one step can be unbounded. The original definition of P systems calls for rules to be applied in a maximally parallel fashion. However, in some cases P systems operating under limited parallelism may be a more reasonable assumption. In this talk, we study the computational power of different variants of P systems operating under the following limited parallelism and synchronization mechanisms. - n-Max-Parallel: at each step, nondeterministically select a maximal subset of at most n rules to apply (this implies that no larger subset is applicable). - ≦ n-Parallel: at each step, nondeterministically select any subset of at most n rules to apply. - n-Parallel: at each step, nondeterministically select any subset of exactly n rules to apply. - Deterministic: the computation path of the systeru is unique; i.e., at each step of the computation, the maximal multiset of rules that is applicable is unique. - k-deterministic: the maximal multiset of rules applicable at each step is at most k. - Sequential: at every step, only one nondeterministically chosen rule instance is applied. P systems considered in this talk include catalytic systems, symport/antiport systems, communicating P systems etc, and their variants. We also consider.
Hsu-Chun Yen
National Taiwan University
国际会议
成都
英文
8-9
2013-11-04（万方平台首次上网日期，不代表论文的发表时间）