( 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
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.
membrane algorithms, cellular automata, Lindenmayer systems, DNA computing, Hamiltonian path, the feasibility of Boolean formulas.

Related Articles