کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438122 | 690229 | 2014 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computational complexity of threshold automata networks under different updating schemes
ترجمه فارسی عنوان
پیچیدگی محاسباتی شبکه های خودکار آستانه تحت برنامه های مختلف به روز رسانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND–OR rule (vertices take the And or the Or logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 559, 20 November 2014, Pages 3–19
Journal: Theoretical Computer Science - Volume 559, 20 November 2014, Pages 3–19
نویسندگان
Eric Goles, Pedro Montealegre,