Premium
On the efficiency of cell‐like and tissue‐like recognizing membrane systems
Author(s) -
GutiérrezNaranjo Miguel A.,
PérezJiménez Mario J.,
RiscosNúñez Agustín,
RomeroCampero Francisco J.
Publication year - 2009
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.20359
Subject(s) - membrane computing , membrane , computer science , satisfiability , context (archaeology) , graph , theoretical computer science , p system , computational complexity theory , algorithm , chemistry , biology , paleontology , biochemistry
Cell‐like recognizing membrane systems are computational devices in the framework of membrane computing inspired from the structure of living cells, where biological membranes are arranged hierarchically. In this paper tissue‐like recognizing membrane systems are presented. The idea is to consider that membranes are placed in the nodes of a graph, mimicking the cell intercommunication in tissues. In this context, polynomial complexity classes associated with recognizing membrane systems can be defined. We recall the definition for cell‐like systems, and we introduce the corresponding complexity classes for the tissue‐like case. Moreover, in this paper two efficient solutions to the satisfiability problem are analyzed and compared from a complexity point of view. © 2009 Wiley Periodicals, Inc.