Alternative representations of P systems solutions to the graph colouring problem. (English) Zbl 1431.68027

Summary: This paper first presents a simulation of the simple kernel P systems solution to the graph 3-colouring problem presented in a previous paper by M. Gheorghe et al. [Int. J. Comput. Math. 90, No. 4, 816–830 (2013; Zbl 1274.68125)], implemented in a programming style named Concurrent ML, which is based on the concept of synchronous communication between logical processing elements. This paper then presents and informally analyses an alternative compact single-cell solution to the same problem using P systems with compound objects (cP systems), which has the benefit of naturally adapting to the use of any number of colours greater than zero – only the specified colour symbols need to be changed. Successful and failing examples of the latter solution are also presented.


68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
05C15 Coloring of graphs and hypergraphs


Zbl 1274.68125
Full Text: DOI


[1] Beigel, R., & Eppstein, D. (2005). 3-Coloring in \[O(1.3289^n)O\](1.3289n) time. Journal of Algorithms, 54(2), 168-204. https://doi.org/10.1016/j.jalgor.2004.06.008. · Zbl 1101.68716
[2] Ben-Ari, M. (2008). Principles of the spin model checker. London: Springer. https://doi.org/10.1007/978-1-84628-770-1. · Zbl 1142.68044
[3] Cooper, J., & Nicolescu, R. (2019). The Hamiltonian cycle and travelling salesman problems in cP systems. Fundamenta Informaticae, 164(2-3), 157-180. https://doi.org/10.3233/FI-2019-1760. · Zbl 1414.68028
[4] Csuhaj-Varjú, E., & Verlan, S. (2011). On generalized communicating P systems with minimal interaction rules. Theoretical Computer Science, 412(1-2), 124-135. https://doi.org/10.1016/j.tcs.2010.08.020. · Zbl 1207.68138
[5] Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., & Riscos-Núñez, A. (2008). A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404(1-2), 76-87. https://doi.org/10.1016/j.tcs.2008.04.005. · Zbl 1151.68016
[6] Gheorghe, M., Ipate, F., Lefticaru, R., Pérez-Jiménez, M. J., urcanu, A., Valencia Cabrera, L., et al. (2013). 3-Col problem modelling using simple kernel P systems. International Journal of Computer Mathematics, 90(4), 816-830. https://doi.org/10.1080/00207160.2012.743712. · Zbl 1274.68125
[7] Hoare, C. A. R. (1985). Communicating sequential processes. Prentice-Hall international series in computer science. Englewood Cliffs: Prentice/Hall International.
[8] Ionescu, M., Păun, G., & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae, 71(2/3), 279-308. · Zbl 1110.68043
[9] Lefticaru, R., Tudose, C., & Ipate, F. (2011). Towards automated verification of P systems using spin. International Journal of Natural Computing Research, 2(3), 1-12. https://doi.org/10.4018/jncr.2011070101. · Zbl 1213.68273
[10] Lewis, R. (2016). A guide to graph colouring. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-25730-3. · Zbl 1330.05002
[11] Nicolescu, R.; Henderson, A.; Graciani, C. (ed.); Riscos-Núñez, A. (ed.); Păun, G. (ed.); Rozenberg, G. (ed.); Salomaa, A. (ed.), An Introduction to cP systems, No. 11270, 204-227 (2018), Cham · Zbl 07002234
[12] Panangaden, P., & Reppy, J. (1997). The essence of concurrent ML (pp. 5-29). New York: Springer. https://doi.org/10.1007/978-1-4612-2274-3_2.
[13] Pérez-Hurtado, I., Orellana-Martín, D., Zhang, G., & Pérez-Jiménez, M. J. (2018). P-lingua compiler: A tool for generating ad-hoc simulators in membrane computing. In M. J. Dinneen, & R. Nicolescu (Eds.), Pre-proceedings of Asian branch of international conference on membrane computing (pp. 149-163). Auckland: Centre for Discrete Mathematics and Theoretical Computer Science. https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/publication-list-bydate.php?selected-date=2018. Accessed 10 Jan 2019.
[14] Pérez-Hurtado, I.; Valencia-Cabrera, L.; Pérez-Jiménez, MJ; Colomer, MA; Riscos-Núñez, A.; Li, K. (ed.); Tang, Z. (ed.); Li, R. (ed.); Nagar, AK (ed.); Thamburaj, R. (ed.), MeCoSim: A general purpose software tool for simulating biological phenomena by means of P systems, 637-643 (2010), Changsha
[15] Păun, G., Pérez-Jiménez, M. J., & Riscos-Núñez, A. (2008). Tissue P systems with cell division. International Journal of Computers Communications & Control, 3(3), 295. https://doi.org/10.15837/ijccc.2008.3.2397.
[16] Reppy, J. H. (1991). CML. ACM SIGPLAN Notices, 26(6), 293-305. https://doi.org/10.1145/113446.113470.
[17] Reppy, J. H. (2007). Concurrent programming in ML. New York: Cambridge University Press. · Zbl 1137.68409
[18] Song, B., Pérez-Jiménez, M. J., Păun, G., & Pan, L. (2016). Tissue P systems with channel states working in the flat maximally parallel way. IEEE Transactions on NanoBioscience, 15(7), 645-656. https://doi.org/10.1109/TNB.2016.2594380.
[19] Verlan, S.; Calude, CS (ed.); Calude, E. (ed.); Dinneen, MJ (ed.), Tissue P systems with minimal symport/antiport, No. 3340, 418-429 (2005), Berlin · Zbl 1117.68375
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.