کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435673 | 689925 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ancestors, descendants, and gardens of Eden in reaction systems
ترجمه فارسی عنوان
اجداد، فرزندان و باغ های ادن در سیستم های واکنش
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محاسبات طبیعی، سیستم های واکنش پیچیدگی محاسباتی، سیستم های دینامیکی گسسته
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved. All the problems studied are intractable, with a complexity that ranges form FPNP[logn]FPNP[logn] to FPSPACE(poly)FPSPACE(poly).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 608, Part 1, 10 December 2015, Pages 16–26
Journal: Theoretical Computer Science - Volume 608, Part 1, 10 December 2015, Pages 16–26
نویسندگان
Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Antonio E. Porreca,