3-COL problem modelling using simple Kernel P systems

Title3-COL problem modelling using simple Kernel P systems
Publication TypeJournal Papers
Year of Publication2013
AuthorsGheorghe, M., Ipate F., Lefticaru R., Pérez-Jiménez M. J., Turcanu A., Valencia-Cabrera L., García-Quismondo M., & Mierla L.
Journal TitleInternational Journal of Computer Mathematics
PublisherTaylor and Francis
Place PublishedLondon, UK
Date Published10/2013

This paper presents the newly introduced class of (simple) kernel P systems ((s)kP systems) and investigates through a 3-colouring problem case study the expressive power and efficiency of kernel P systems. It describes two skPsystems that model the problem and analyzes them in terms of efficiency and complexity. The skP models prove to be more succinct (in terms of number of rules, objects, number of cells and execution steps) than the corresponding tissue P system, availablein the literature, that solves the same problem, at the expense of a greater length of the rules.

Keywords3-colour problem, Formal Verification, kernel P systems, Membrane computing, Tissue P Systems
Impact Factor



173/247 - Q3

ISSN Number0020-7160