New Frontiers of the Efficiency in Tissue P Systems

摘要：

　　In Membrane Computing,cell division and cell separation provide two different mechanisms to generate an exponential workspace in polynomial time.This paper deals with the computational efficiency of tissue P systems providing two new frontiers for the tractability of problems,assuming P≠NP.The frontiers refer to the length of communication rules in tissue P systems and also refer to the kind of rules (separation versus division) when we restrict the length of communication rules to two.

关键词： Membrane Computing Tissue P System Cell Separation Communication rule Computational Complexity

作者: Linqiang Pan Mario J.Pérez-Jiménez Agustín Riscos-Nú(n)ez Miquel Rius-Font

作者单位: Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Enginee Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Unive Department of Applied Mathematics Ⅳ Universitat Politécnica de Catalunya, Spain

会议类型: 国际会议

会议名称: Asian Conference on Membrane Computing (2012亚洲膜计算国际会议)(ACMC2012)

会议地点: 武汉

会议语种:英文

页码: 61-73

在线出版日期: 2012-10-15（万方平台首次上网日期，不代表论文的发表时间）