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

چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 529, 10 April 2014, Pages 69–81
نویسندگان
Artiom Alhazov, Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron,