On Communication Complexity in Evolution-Communication P Systems
On Communication Complexity in Evolution-Communication P Systems
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
H. Adorna;G. Paun;M. D. Jiménez
中科院分区：
文献类型：
--
作者：
H. Adorna;G. Paun;M. D. Jiménez
为了寻找P系统的通信复杂性理论，我们考虑所谓的进化通信（EC简称）P系统，其中对象通过多集重写规则进化，而不需要目标命令，并通过同向/反向规则穿过膜。我们首先提出了一种方法来衡量通信成本的“量子的能量”（产生的进化规则和）消耗的通信规则。证明了具有这种代价的ECP系统在所有三种情况下都是图灵完备的：通信优先级，混合规则没有任何类型的优先级，进化优先级（在普适性证明中，通信代价以这种顺序增加）。通信复杂性的更适当的措施，然后定义为动态参数，计算通信步骤或在计算过程中使用的通信规则的数量（和权重）。这样的参数可以用在三种方式：作为P系统的属性（考虑具有给定通信复杂度的系统生成的数集的族），作为施加在计算上的条件（只接受那些具有给定阈值的通信复杂度的计算），以及作为标准复杂度度量（定义可以114 H. Adorna等人的方法可以用具有有限复杂性的P系统来求解）。因为我们忽略了进化步骤，所以在所有三种情况下，考虑从有限复杂度阈值开始的层次结构是有意义的。我们只给出了一些关于这些层次结构的初步结果（例如，证明它们的较低层次已经包含复杂的-例如，非半线性集），我们留下了许多问题，
Looking for a theory of communication complexity for P systems, we consider here so-called evolution-communication (EC for short) P systems, where objects evolve by multiset rewriting rules without target commands and pass through membranes by means of symport/antiport rules. We first propose a way to measure the communication costs by means of “quanta of energy” (produced by evolution rules and) consumed by communication rules. EC P systems with such costs are proved to be Turing complete in all three cases with respect to the relation between evolution and communication operations: priority of communication, mixing the rules without priority for any type, priority of evolution (with the cost of communication increasing in this ordering in the universality proofs). More appropriate measures of communication complexity are then defined, as dynamical parameters, counting the communication steps or the number (and the weight) of communication rules used during a computation. Such parameters can be used in three ways: as properties of P systems (considering the families of sets of numbers generated by systems with a given communication complexity), as conditions to be imposed on computations (accepting only those computations with a communication complexity bounded by a given threshold), and as standard complexity measures (defining the class of problems which can 114 H. Adorna et al. be solved by P systems with a bounded complexity). Because we ignore the evolution steps, in all three cases it makes sense to consider hierarchies starting with finite complexity thresholds. We only give some preliminary results about these hierarchies (for instance, proving that already their lower levels contain complex – e.g., non-semilinear – sets), and we leave open many problems and