More about authors
Ershov Nikolay Mikhailovich PhD in physics and mathematics, senior research associate, Faculty of Computational Mathematics and Cybernetics
For read the full article, please, register or log in
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:
. . // . / . . . - . 12. - . . ; , 2011. - . 39-45.
. ., . . // : , , . - 2014. - № 2. - . 359-362.
. , . , . , - . , . : , 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.