Replicative-Distribution Rules in P Systems with Active Membranes

Хэвлэлийн нэр: Theoretical Aspects of Computing - ICTAC 2004 Volume 3407 of the series Lecture Notes in Computer Science, Springer

Зохиогч:  И.Цэрэн-Онолт

Хамтран зохиогч: Tseren-Onolt Ishdorj, Mihai Ionescu

Хэвлүүлсэн огноо: 2005-08-08

Хуудас дугаар: 69-84

Өгүүллийн хураангуй: P systems (known also as membrane systems) are biologically motivated theoretical models of distributed and parallel computing. The two most interesting questions in the area are completeness (solving every solvable problem) and efficiency (solving a hard problem in feasible time). In this paper we define a general class of P systems covering some biological operations with membranes. We introduce a new operation, called replicative-distribution, into P systems with active membranes. This operation is well motivated from a biological point of view, and elegant from a mathematical point of view. It is both computationally powerful and efficient. More precisely, the P systems with active membranes using replicative-distribution rules can compute exactly what Turing machines can compute, and can solve NP-complete problems, particularly SAT, in linear time.

Өгүүллийн төрөл: Мэргэжлийн түвшинд хянагддаг сэтгүүл

Өгүүллийн зэрэглэл: Гадаад

Түлхүүр үг: #NP-complete problems #Membrane systems

Өгүүлэл нэмсэн: И.Цэрэн-Онолт

Монгол Улсын Шинжлэх Ухаан Технологийн Их Сургууль © 2020