کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875846 | 1441988 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The counting power of P systems with antimatter
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P#P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class Pâ¥#P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass Pâ¥NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 701, 21 November 2017, Pages 161-173
Journal: Theoretical Computer Science - Volume 701, 21 November 2017, Pages 161-173
نویسندگان
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron,