DNA and Membrane Algorithms for SAT

Issue title: Membrane Computing (WMC-CdeA2001)

Article type: Research Article

Authors: Manca, Vincenzo

Affiliations: Università di Pisa, Dipartimento di Informatica, Corso Italia, 40 - 56125 Pisa, Italy

Abstract: Some DNA algorithms proposed in the literature for propositional satisfiability (SAT) are analyzed. In the class of 'extract model' the two sub-classes of 'literal string' and 'clause string' algorithms are compared and a new formulation of these algorithms is given in terms of membrane systems. Then, the duality between literal string and clause string formulation of SAT is expressed by means of 'singleton matrices' that introduce another membrane algorithm for SAT. The analysis developed suggests the perspective of membrane systems as problem-solving agents based on molecule localization, transformation, and propagation.

Keywords: Satisfiability, DNA Computing, Membrane Systems, Molecular Computing, Unconventional Computing Models

Journal: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 205-221, 2002