DNA and Membrane Algorithms for SAT

• Autorzy: Manca V.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

propositional satisfiability; DNA computing; membrane system; molecular computing; Unconventional Computing Models

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 49, nr 1-3
• Strony: 205--221
• Opis fizyczny: bibliogr. 29 poz.

Twórcy

autor

Manca V.

• Dipartimento di Informatica, Universita diPisa, Corso Italia, 40- 56125 Pisa, Italy,

Bibliografia

• [1] L.M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266 (Nov. 1994), 1021-1024.
• [2] R. S. Brainch, C. Johnson, P.W.K. Rothemund, D. Hwang, N. Chelyapov, L.M. Adleman, Solutions of a Sat¬isfiability Problem on a Gel-Based DNA Computer, Sixth International Meeting on DNA Based Computers, Leiden Center for Natural Computing (A. Condon G. Rozenberg, eds.), Leiden, 2000.
• [3] K. Chen, E. Winfree, Error Correction in DNA Computing: Misclassification and Strand Loss, in [29], 49-63.
• [4] M. Fitting, First-Order Logic and Automated Theorem Proving, Springer-Verlag, New-York, 1996.
• [5] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.
• [6] M. Hagiya, Perspectives on Molecular Computing, New Generat. Comput., 17 (1999), 131-151.
• [7] T. Head, X. Chen, M.J. Nichols, M. Yamamura, S. Gal, Aqueous Solutions of Algorithmic Problems: Em¬phasizing Knights on a 3x3, in [9], 219-230.
• [8] N. Jonoska, S. A. Karl, M. Saito, Three Dimensional DNA Structures in Computing, BioSystems, 52 (1999), 242-245.
• [9] N. Jonoska, N. Seeman, eds., Pre-Proc. 7th International Meeting on DNA Based Computers, Tampa, U.S.A. (FL), 2001.
• [10] S. A. Kauffman, Investigations, Oxford University press, London, 2000.
• [11] L. Landweber, E. Baum, eds., DNA Based Computers II, DIMACS Series 44, American Math. Society, Providence RI, 1999.
• [12] R. Lipton, DNA Solutions of hard computational problems, Science, 268 (1995), 242-245 [13] V. Manca, Monoidals for Molecules and Membranes, Romanian Journal of Information Science and Technology , 1-2 (2001), 155-170.
• [14] V. Manca, Di Gregorio S., Lizzari D., Vallini G., Zandron C., A DNA Algorithm for 3-SAT(ll,20), in [9], 167-178.
• [15] V. Manca, Membrane Algorithms for Propositional Satisfiability, Pre-proc. Workshop on Membrane Computing, Curtea de Arges, Romania, TR 17, GRLMC, Univ. Rovirai Virgili, Tarragona (Spain), 2001, 181-192.
• [16] V. Manca, C. Zandron, A Clause String DNA Algorithm for SAT, in “Proc. 7th Int. M eeting on DNA Based Computers, N Jonoska, N.Seeman (eds.), Springer-Verlag, to appear” .
• [17] Gh. P3un, G. Rozenberg, A. Salomaa, DNA Computing: New Computing Paradigms, Springer-Verlag, Berlin, 1998.
• [18] Gh. P3un, Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143, and Turku Center for Computer Science-TUCS Report No 208,1 998 (www.tucs.fi).
• [19] Gh. Paun,, G. Rozenberg, A. Salomaa, Membrane Computing with External Output, Fundamenta Informati-cae, 41, 3 (2000), 259 -266.
• [20] Gh. P3un, Computing with Membranes. An Introduction, Bulletin of the EATCS, 67 (Febr. 1999), 139-152.
• [21] Gh. P3un, P Systems with Active Membranes: Attacking NP Complete Problems, J. Automata Languages and Combinatorics, 6, 1 (2001), 75-90 .
• [22] Gh. P3un, From Cells to Computers: Computing with Membranes (P Systems), BioSystems, 59, 3 (2001), 139-158 .
• [23] H. Rubin, D. Wood, DNA Based Computers III, DIMACS Series 48, American Math. Society, Providence RI, 1999.
• [24] K. Sakamoto, H. Gounzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, M. Hagiya, Molecular Computation by DNA Hairpin Formation, Science,'288 (May 2000), 12231226.
• [25] K. Sakamoto, D. Kiga, K. Komiya, H. Gounzu, S. Yokoyama, S. Ikeda, H. Sugiyama, M. Hagiya, State Transitions by Molecules, BioSystems, 52 (1999), 81-91.
• [26] B. Selman, D. Mitchel, H. Levesque, Generating Hard Satisfiability Problem, Artificial Intelligence, 81 (1996), 17-29.
• [27] Y. Takenaka, A. Hashimoto, A Proposal of DNA Computing on Beads and its Application to SAT Problems, in [9], 33 1-3 39.
• [28] H. Yoshida, A. Suyam a, Solutions to 3-SAT by Breadth First Search, in [29], 9 -22 .
• [29] E. Winfree E., D.K. Gifford, DNA Based Computers V, DIMACS Series 54, American Math. Society, Provi¬dence RI, 2001.