کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334318 | 690377 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computationally universal P systems without priorities: two catalysts are sufficient
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Computationally universal P systems without priorities: two catalysts are sufficient Computationally universal P systems without priorities: two catalysts are sufficient](/preview/png/10334318.png)
چکیده انگلیسی
The original model of P systems with symbol objects introduced by PÄun was shown to be computationally universal, provided that catalysts and priorities of rules are used. By reduction via register machines SosÃk and Freund proved that the priorities may be omitted from the model without loss of computational power. Freund, Oswald, and SosÃk considered several variants of P systems with catalysts (but without priorities) and investigated the number of catalysts needed for these specific variants to be computationally universal. It was shown that for the classic model of P systems with the minimal number of two membranes the number of catalysts can be reduced from six to five; using the idea of final states the number of catalysts could even be reduced to four. In this paper we are able to reduce the number of catalysts again: two catalysts are already sufficient. For extended P systems we even need only one membrane and two catalysts. For the (purely) catalytic systems considered by Ibarra only three catalysts are already enough.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 251-266
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 251-266
نویسندگان
Rudolf Freund, Lila Kari, Marion Oswald, Petr SosÃk,