Mon, 11/23/2009 - 10:24 — mmartinez

Title | Efficient simulation of tissue-like P systems by transition cell-like P systems |

Publication Type | Journal Papers |

Year of Publication | 2009 |

Authors | Díaz-Pernil, D., Pérez-Jiménez M. J., & Romero-Jiménez Á. |

Journal Title | Natural Computing |

Publisher | Springer Verlag |

Place Published | Amsterdam, Netherlands |

Volume | 8 |

Pages | 797-806 |

Date Published | 12/2009 |

Abstract | In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution, communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of basic cell-like P systems to this kind of tissue-like P systems. |

URL | http://dx.doi.org/10.1007/s11047-008-9102-z |

Issue | 4 |

ISSN Number | 1567-7818 |

DOI | 10.1007/s11047-008-9102-z |