Time-Free Solution to 3-Coloring Problem Using Tissue P Systems  

作　　者：NIU Yunyun XIAO Jianhua JIANG Yun 

机构地区：[1]School of Information Engineering,China University of Geosciences in Beijing [2]The Research Center of Logistics,Nankai University [3]School of Computer Science and Information Engineering,Chongqing Technology and Business University

出　　处：《Chinese Journal of Electronics》2016年第3期407-412,共6页电子学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.61127005,No.61373066);the Natural Science Foundation Project of CQ CSTC(No.cstc2012jj A40059);the Science Research Fund of Chongqing Technology and Business University(No.2013-56-01)

摘　　要：In most of traditional P systems, each rule has the same execution time. That way of using the rules is not quite realistic from a biological point of view, because external conditions always change in an unpredicted manner such that different reaction may take different time to execute. In this work, we investigate the computation efficiency of tissue P systems by removing the restriction that each rule should complete in one time unit. The timed tissue P system is constructed by adding a time mapping to the rules to specify the execution time for each rule.A uniform and time-free solution to 3-coloring problem is proposed, where the execution time of the computational processes involved can vary arbitrarily and the output produced is always the same.In most of traditional P systems, each rule has the same execution time. That way of using the rules is not quite realistic from a biological point of view, because external conditions always change in an unpredicted manner such that different reaction may take different time to execute. In this work, we investigate the computation efficiency of tissue P systems by removing the restriction that each rule should complete in one time unit. The timed tissue P system is constructed by adding a time mapping to the rules to specify the execution time for each rule.A uniform and time-free solution to 3-coloring problem is proposed, where the execution time of the computational processes involved can vary arbitrarily and the output produced is always the same.

关 键 词：Membrane computing Tissue P system Time-free solution 3-Coloring problem 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]