کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437916 690206 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-confluence in divisionless P systems with active membranes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Non-confluence in divisionless P systems with active membranes
چکیده انگلیسی

We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class .

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issue 6, 6 February 2010, Pages 878-887