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

NIU Yunyun; XIAO Jianhua; JIANG Yun

doi:10.1049/cje.2016.05.003

Volume 25 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(3): 407-412

NIU Yunyun, XIAO Jianhua, JIANG Yun, “Time-Free Solution to 3-Coloring Problem Using Tissue P Systems,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 407-412, 2016, doi: 10.1049/cje.2016.05.003

Citation:

NIU Yunyun, XIAO Jianhua, JIANG Yun, “Time-Free Solution to 3-Coloring Problem Using Tissue P Systems,” Chinese Journal of Electronics, vol. 25, no. 3, pp. 407-412, 2016, doi: 10.1049/cje.2016.05.003

Citation:

PDF( 200 KB)

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

doi: 10.1049/cje.2016.05.003

1.
School of Information Engineering, China University of Geosciences in Beijing, Beijing 100083, China;
2.
The Research Center of Logistics, Nankai University, Tianjin 300071, China;
3.
School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61127005, No.61373066), the Natural Science Foundation Project of CQ CSTC (No.cstc2012jjA40059), and the Science Research Fund of Chongqing Technology and Business University (No.2013-56-01).

More Information

Corresponding author: XIAO Jianhua was born in 1979. He graduated from Huazhong University of Science and Technology in 2008. He is currently a lecture at Nankai University, Tianjin, China. His research interests include combinatorial optimization, Bio-inspired computation and logistics optimization. (Email: jhxiao@nankai.edu.cn)
Received Date: 2014-04-08
Rev Recd Date: 2014-06-11
Publish Date: 2016-05-10

Abstract

Abstract

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

FullText(HTML)

References(36)

References

G. P?un, "Computing with membranes", Journal of Computer and System Sciences, Vol.61, No.1, pp.108-143, 2000.

V. Manca, A. Castellini, G. Franco, et al., "Metabolic P systemsa discrete model for biological dynamics", Chinese Journal of Electronics, Vol.22, No.4, pp.717-723, 2013.

M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, et al., "On the power of dissolution in P systems with active membranes", Lecture Notes in Computer Science, Vol.3850, pp.224-240, 2006.

C. Martín Vide, J. Pazos, G. P?un, et al., "Tissue P systems", Theoretical Computer Science, Vol.296, No.2, pp.295-326, 2003.

X. Zhang, S. Wang, Y. Niu, et al., "Tissue P systems with cell separation: Attacking the partition problem", Science China Information Sciences, Vol.54, No.2, pp.293-304, 2011.

M. Ionescu, G. P?un and T. Yokomori, "Spiking neural P systems", Fundamenta Informaticae, Vol.71, pp.279-308, 2006.

L. Pan and G. P?un, "Spiking neural P systems: An improved normal form", Theoretical Computer Science, Vol.411, No.6, pp.906-918, 2010.

G. Zhang, F. Zhou, X. Huang, et al., "A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems", Journal of Universal Computer Science, Vol.18, No.13, pp.1821-1841, 2012.

Y. Chen, G. Zhang, T.Wang, et al., "Automatic design of P systems for five basic arithmetic operations within one framework", Chinese Journal of Electronics, Vol.23, No.2, pp.302-304, 2014.

G. Zhang, J. Cheng, M. Gheorghe, et al., "A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems", Applied Soft Computing, Vol.13, No.3, pp.1528- 1542, 2013.

G. Zhang, H. Rong, J. Cheng, et al., "A Population-membranesystem- inspired evolutionary algorithm for distribution network reconfiguration", Chinese Journal of Electronics, Vol.23, No.3, pp.437-441, 2014.

P. Guo, H. Chen and H. Zheng, "Arithmetic expression evaluations with membranes", Chinese Journal of Electronics, Vol.23, No.3, pp.55-60, 2014.

L. Pan, D.P. Daniel and M.J. Pérez-Jiménez, "Computation of Ramsey numbers by P system with active membranes", International Journal of Foundations of Computer Science, Vol.22, No.1, pp.29-38, 2011.

L. Pan, G. P?un and M.J. Pérez-Jiménez, "Spiking neural P systems with neuron division and budding", Science China Information Science, Vol.54, No.8, pp.1596-1607, 2011.

A. Alhazov, C. Martín-Vide and L. Pan, "Solving a PSPACEcomplete problem by recognizing P systems with restricted active membranes", Fundamenta Informaticae, Vol.58, No.2, pp.66-77, 2003.

T. Ishdorj, A. Leporati, L. Pan, et al., "Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with precomputed resources", Theoretical Computer Science, Vol.411, No.25, pp.2345-2358, 2010.

L. Pan and C. Martín-Vide, "Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes", Journal of Parallel and Distributed Computing, Vol.65, No.12, pp.1578-1584, 2005.

G. P?un, M.J. Pérez-Jiménez and A. Riscos-Núñez, "Tissue P systems with cell division", International Journal of Computers, Communications and Control, Vol.3, No.3, pp.295-303, 2008.

L. Pan, A. Alhazov and T. Ishdorj, "Further remarks on P systems with active membranes, separation, merging, and release rules", Soft Computing, Vol.9, No.9, pp.686-690, 2005.

L. Pan and T. Ishdorj, "P systems with active membranes and separation rules", Journal of Universal Computer Science, Vol.10, No.5, pp.630-649, 2004.

M. Mutyam and K. Krithivasan, "P systems with membrane creation: Universality and efficiency", Lecture Notes in Computer Science, Vol.2055, pp.276-287, 2001.

G. P?un, Membrane Computing: An Introduction, Springer- Verlag, Berlin, Germany, 2002.

G. P?un, G. Rozenberg and A. Salomaa, Handbook of Membrane Computing, Oxford University Press, Oxford, UK, 2009.

G. Ciobanu, M.J. Pérez-Jiménez and G. P?un, Applications of Membrane Computing, Springer-Verlag, Berlin, Germany, 2006.

M. Tu, J. Wang, H. Peng, et al., "Application of adaptive fuzzy spiking neural P systems in fault diagnosis of power systems", Chinese Journal of Electronics, Vol.23, No.1, pp.87-92, 2014.

L. Pan and M.J. Pérez-Jiménez, "Computational complexity of tissue-like P systems", Journal of Complexity, Vol.26, No.3, pp.296-315, 2010.

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, et al., "Solving subset sum in linear time by using tissue P systems with cell division", Lecture Notes in Computer Science, Vol.4527, pp.170-179, 2007.

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, et al., "Solving the partition problem by using tissue-like P systems with cell division", Proc. of 6th Brainstorming Week on Membrane Computing, Sevilla, Spain, pp.124-134, 2008.

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, et al., "A linear-time tissue P system based solution for the 3- coloring problem", Electronic Notes in Theoretical Computer Science, Vol.171, No.2, pp.81-93, 2007.

M. Cavaliere and D. Sburlan, "Time-independent P systems", Lecture Notes in Computer Science, Vol.3365, pp.239-258, 2005.

M. Cavaliere and V. Deufemia, "Further results on time-free P systems", International Journal of Foundations of Computer Science, Vol.17, No.1, pp.69-89, 2006.

L. Pan, X. Zeng and X. Zhang, "Time-free spiking neural P systems", Neural Computation, Vol.23, No.5, pp.1320-1342, 2011.

M. Cavaliere, "Time-free solution to hard computational problems", Proc. of 10th Brainstorming Week on Membrane Computing, Seville, Spain, pp.204-210, 2012.

T. Song, H. Zheng, J. He, et al., "Time-free solution to Hamilton path problems using P systems with d-division", Journal of Applied Mathematics, Article ID 975798, 7 pages, doi:10.1155/2013/975798, 2013.

T. Song, L.F.M. Macías-Ramos, L. Pan, et al., "Time-free solution to SAT problem using P systems with active membranes", Theoretical Computer Science, Vol.529, pp.61-68, 2014.

T. Song, L. Luo, J. He, et al., "Solving subset sum problems by time-free spiking neural P systems", Applied Mathematics & Information Sciences, Vol.8, No.1, pp.327-332, 2014.

Relative Articles

Supplements(0)

Cited By

Proportional views