SCIENTIFIC SCHOOL OF PROFESSOR A. M. POPOV

Implementation of membrane algorithmswith markov systems

N. M. Ershov

Lomonosov Moscow State University

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.

Keywords: membrane algorithms, cellular automata, Lindenmayer systems, DNA computing, Hamiltonian path, Boolean satisfiability problem.

Bibliographic databases:

•