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
Volume90
Pages816-830
Date Published10/2013
Abstract

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
URLhttp://dx.doi.org/10.1080/00207160.2012.743712
Issue4
Impact Factor

0.542

Ranking

173/247 - Q3

ISSN Number0020-7160
DOI10.1080/00207160.2012.743712