کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952268 | 1442025 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computational complexity of finite asynchronous cellular automata
ترجمه فارسی عنوان
پیچیدگی محاسباتی از اتوماتای سلولی ناسازگار محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محاسبات طبیعی، اتوماتای سلول آسنکرون، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or Î 2P-complete (universal version) for higher dimension.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 664, 15 February 2017, Pages 131-143
Journal: Theoretical Computer Science - Volume 664, 15 February 2017, Pages 131-143
نویسندگان
Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca,