Computational complexity of tissue-like P systems

TitleComputational complexity of tissue-like P systems
Publication TypeJournal Papers
Year of Publication2010
AuthorsPan, L., & Pérez-Jiménez M. J.
Journal TitleJournal of Complexity
PublisherElsevier
Volume26
Pages296-315
Date Published06/2010
Abstract

Membrane systems, also called P systems, are biologically inspired theoretical models of distributed and parallel computing. This paper presents a new class of tissue-like P systems with cell separation, a feature which allows the generation of new workspace. We study the efficiency of the class of P systems and draw a conclusion that only tractable problems can be efficiently solved by using cell separation and communication rules with the length of at most 1. We further present an efficient (uniform) solution to SAT by using cell separation and communication rules with length at most 6. We conclude that a borderline between efficiency and non-efficiency exists in terms of the length of communication rules . We discuss future research topics and open problems.

KeywordsCell separation, Membrane computing, SAT, Tissue P Systems
URLhttp://dx.doi.org/10.1016/j.jco.2010.03.001
Issue3
Impact Factor

0.781

Ranking

65/97 - Q3

ISSN Number0885-064X
DOIdx.doi.org/10.1016/j.jco.2010.03.001