Trading polarizations for bi-stable catalysts in P systems with active membranes

TitleTrading polarizations for bi-stable catalysts in P systems with active membranes
Publication TypeJournal Papers
Year of Publication2005
AuthorsPérez-Jiménez, M. J., & Romero-Campero F. J.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-25080-7
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume3365
Pages373-388
Abstract

In the last time, several efforts have been made in order to remove polarizations of membranes from P systems with active membranes; the present paper is a contribution in this respect. In order to compensate the loss of power represented by avoiding polarizations, we use bi-stable catalysts. Polarizationless systems with active membranes which use bi-stable catalysts are proven to be computationally complete and able to solve efficiently NP-complete problems. In this paper we present a solution to SAT in linear time. In order to illustrate the presented solution, we also provide a simulation with CLIPS.

URLhttp://www.springerlink.com/content/dc6hae6hbe6541vq/?p=742d49e299334301a36583e895d4c151&pi=23
ISSN Number0302-9743