کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437519 690151 2011 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Traced communication complexity of cellular automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Traced communication complexity of cellular automata
چکیده انگلیسی

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 30, 8 July 2011, Pages 3906-3916