IMPLEMENTATION OF MEMBRANE ALGORITHMSWITH MARKOV SYSTEMS
( Pp. 36-46)
More about authors
Ershov Nikolay M.
Cand. Sci. (Phys.-Math.); senior research at the Faculty of Computational Mathematics and Cybernetics
Lomonosov Moscow State University
Moscow, Russian Federation
Lomonosov Moscow State University
Moscow, Russian Federation
Abstract:
The paper is devoted to the investigation of algorithmic possibilities of Markov systems by the example of solving two NP-complete problems - searching for a Hamiltonian path and the problem of the satisfiability of a Boolean formula. The issues of realization of membrane algorithms for solving these problems having polynomial time dependence depend on the size of the problem are considered. The results of a numerical investigation of the proposed algorithms are presented.
How to Cite:
Ershov N.M., (2017), IMPLEMENTATION OF MEMBRANE ALGORITHMSWITH MARKOV SYSTEMS. Computational Nanotechnology, 2 => 36-46.
Reference list:
Ershov N. M. Nedeterminirovannyy membrannyy algoritm poiska gamil tonova puti // Programmnye sistemy i instrumenty. Tematicheskiy sbornik / Pod red. L. Korolev. - T. 12. - Izdatel skiy otdel fakul teta VMK MGU imeni M.V. Lomonosova; MAKS Press Moskva, 2011. - S. 39-45.
Ershov N. M., Kravchuk A. V. Diskretnoe modelirovanie s pomoshch yu stokhasticheskikh kletochnykh avtomatov // Vestnik Rossiyskogo universiteta druzhby narodov: Seriya Matematika, informatika, fizika. - 2014. - № 2. - S. 359-362.
G. Paun, G. Rozenberg, A. Salomaa, DNK-komp yuter. Novaya paradigma vychisleniy, M. : Mir, 2003.
Leonard M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266, 11, pp. 1021-1024, 1994.
K.L. Chung and F. AitSahlia. Elementary Probability Theory: With Stochastic Processes and an Introduction to Mathematical Finance. Undergraduate Texts in Mathematics. Springer, 2003.
Peter Dittrich, Jens Ziegler, and Wolfgang Banzhaf. Artificial chemistries - a review. Artif. Life, 7(3):225-275, June 2001.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.
Adam Obtulowicz. Deterministic P systems for solving SAT problem. Romanian Journal of Information Science and Technology, 4(1-2):195-202, 2001.
Gheorghe Paun. Computing with membranes. An introduction. Bulletin of the EATCS, (67):139-152, February 1999.
Gheorghe Paun. P systems with active membranes: Attacking NP-Complete problems. Journal of Automata, Languages and Combinatorics, 6(1):75-90, 2001.
Gheorghe Paun and Grzegorz Rozenberg. A guide to membrane computing. Theoretical Computer Science, 287(1):73-100, September 2002.
Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The algorithmic beauty of plants. Springer-Verlag New York, Inc., NY, USA, 1996.
Grzegorz Rozenberg and Arto Salomaa. Mathematical Theory of L Systems. Academic Press, Inc., Orlando, FL, USA, 1980.
Tommaso Toffoli and Norman Margolus. Cellular automata machines: a new environment for modeling. MIT Press, Cambridge, MA, USA, 1987.
Ershov N. M., Kravchuk A. V. Diskretnoe modelirovanie s pomoshch yu stokhasticheskikh kletochnykh avtomatov // Vestnik Rossiyskogo universiteta druzhby narodov: Seriya Matematika, informatika, fizika. - 2014. - № 2. - S. 359-362.
G. Paun, G. Rozenberg, A. Salomaa, DNK-komp yuter. Novaya paradigma vychisleniy, M. : Mir, 2003.
Leonard M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266, 11, pp. 1021-1024, 1994.
K.L. Chung and F. AitSahlia. Elementary Probability Theory: With Stochastic Processes and an Introduction to Mathematical Finance. Undergraduate Texts in Mathematics. Springer, 2003.
Peter Dittrich, Jens Ziegler, and Wolfgang Banzhaf. Artificial chemistries - a review. Artif. Life, 7(3):225-275, June 2001.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.
Adam Obtulowicz. Deterministic P systems for solving SAT problem. Romanian Journal of Information Science and Technology, 4(1-2):195-202, 2001.
Gheorghe Paun. Computing with membranes. An introduction. Bulletin of the EATCS, (67):139-152, February 1999.
Gheorghe Paun. P systems with active membranes: Attacking NP-Complete problems. Journal of Automata, Languages and Combinatorics, 6(1):75-90, 2001.
Gheorghe Paun and Grzegorz Rozenberg. A guide to membrane computing. Theoretical Computer Science, 287(1):73-100, September 2002.
Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The algorithmic beauty of plants. Springer-Verlag New York, Inc., NY, USA, 1996.
Grzegorz Rozenberg and Arto Salomaa. Mathematical Theory of L Systems. Academic Press, Inc., Orlando, FL, USA, 1980.
Tommaso Toffoli and Norman Margolus. Cellular automata machines: a new environment for modeling. MIT Press, Cambridge, MA, USA, 1987.
Keywords:
membrane algorithms, cellular automata, Lindenmayer systems, DNA computing, Hamiltonian path, the feasibility of Boolean formulas.
Related Articles
