An efficient time-free solution to SAT problem by P systems with proteins on membranes

TitleAn efficient time-free solution to SAT problem by P systems with proteins on membranes
Publication TypeJournal Papers
Year of Publication2016
AuthorsSong, B., Pérez-Jiménez M. J., & Pan L.
Journal TitleJournal of Computer and System Sciences
PublisherElsevier
Place PublishedAmsterdam (The Netherlands)
Volume82
Pages1090-1099
Date Published04/2016
Abstract

P systems with proteins on membranes are a class of bio-inspired computing models, where the execution of each rule completes in exactly one time unit. However, in living cells, the execution time of biochemical reactions is difficult to know precisely because of various uncontrollable factors. In this work, we present a time-free uniform solution to SAT problem by P systems with proteins on membranes in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, and the P systems are constructed from the sizes of instances.

KeywordsP system; Membrane protein; Time-free uniform solution; SAT
URLhttp://www.sciencedirect.com/science/article/pii/S0022000016300113
Issue6
ISSN Number0022-0000
DOIdoi:10.1016/j.jcss.2016.03.008