A theoretical model of the Shapiro finite state automaton built on DNA

• Autorzy: Krasiński T. , Sakowski S.

Warianty tytułu

PL

Teoretyczny model automatu skończonego Shapiro opartego na DNA

• Języki publikacji: EN

Abstrakty

EN

In the paper a theoretical model (in the form of a splicing system) of a DNA computing machine, constructed in Weizmann Institute of Science by Benenson, Adar, Paz-Elizur, Livneh and Shapiro [4] is given. This splicing system exactly reflects the action of the DNA computer. We describe in detail finite state automaton built on DNA and give its scheme of computation.

PL

W obecnie prowadzonych pracach nad nanosystemami informatyki bada się możliwość wykorzystania DNA do kodowania i przetwarzania informacji. W artykule opracowany jest teoretyczny model (w postaci systemu splatania „splicing system") DNA komputera skonstruowanego w Instytucie Weizmanna przez zespół: Benenson, Adar, Paz-Elizur, Livneh i Shapiro. Model ten dokładnie odzwierciedla działanie tego DNA komputera. Omówiono działanie automatu skończonego opartego na DNA oraz podano jego schemat ideowy działania.

Słowa kluczowe

EN

splicing system; molecular computing; DNA strand; finite automaton

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2006
• Tom: Vol. 18, nr 3
• Strony: 161--174
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Krasiński T.

autor

Sakowski S.

• Faculty of Mathematics University of Łódź 90-238 Łódź, Banacha 22, Poland,

Bibliografia

• [1] Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 226, 1021-1024 (1994).
• [2] Amos, M.: Theoretical and Experimental DNA Computation. Springer. Berlin, Heidelberg, New York. 2005.
• [3] Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z., Shapiro, E.: Programmable and autonomous computing machine made of biomolecules. Nature 414, 430-434 (2001).
• [4] Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z., Shapiro, E.: DNA molecule provides a computing machine with both data and fuel. PNAS 100, 2191-2196 (2003).
• [5] Boneh, D., Dunworth, C., Lipton, R.J., Sgall, J.: On the computational Power of DNA. Discrete App. Math., 71, 79-94 (1996).
• [6] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
• [7] Kari, L.: DNA Computing. The arrival of biological mathematics. The Mathematical Intelligencer 192, 9-22 (1997).
• [8] Kari, L., Paun G., Rozenberg G., Salomaa A., Yu S.: DNA computing, sticker systems and universality. Acta Informatica, 35, 401-420(1998).
• [9] Kari, L., Kitto, R., Thirrn, G.: Codes, involutions and DNA encoding. Lecture Notes in Computer Science 2300, 376-393 (2002).
• [10] Paun, G.: On the power of the splicing operation. Internationals Journal of Computer Mathematics 59, 27-35 (1995).
• [11] Paun, G., Rozenberg G., Salomaa, A.: DNA Computing. New Computing Paradigma. Springer. Berlin, Heidelberg, New York 1998.
• [12] Unold, O., Troć M., Dobosz T., Trusiewicz A.: Extended molecular computing model. WSEAS Trans. Biol. Biomed. 1 (2004), 15-19.