کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434383 689724 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Space complexity equivalence of P systems with active membranes and Turing machines
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Space complexity equivalence of P systems with active membranes and Turing machines
چکیده انگلیسی

We prove that arbitrary single-tape Turing machines can be simulated by uniform families of P systems with active membranes with a cubic slowdown and quadratic space overhead. This result is the culmination of a series of previous partial results, finally establishing the equivalence (up to a polynomial) of many space complexity classes defined in terms of P systems and Turing machines. The equivalence we obtained also allows a number of classic computational complexity theorems, such as Savitch's theorem and the space hierarchy theorem, to be directly translated into statements about membrane systems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 529, 10 April 2014, Pages 69–81
نویسندگان
, , , , ,