کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952308 1442030 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Leader election on two-dimensional periodic cellular automata
ترجمه فارسی عنوان
انتخاب رهبران در اتوماتای ​​سلولی دوره ای دو بعدی
کلمات کلیدی
اتوماتای ​​سلولی، انتخاب رهبر پیکربندی دو دوره ای، کلاس های هم ارز، محاسبات یکنواخت،
ترجمه چکیده
این مقاله به بررسی توان محاسباتی اتوماتای ​​سلولی دو بعدی بر روی تنظیمات دوره ای می پردازد. در بعضی موارد نتایج یک مقاله مشابه به مورد یک بعدی اختصاص یافته است. دقیق تر، ما یک الگوریتم ارائه می دهیم که حداقل الگوی شبکه ای را محاسبه می کند، یعنی یک الگوی حداقل و دو بردار ترجمه که می تواند برای تزیین کل پیکربندی استفاده شود. این مشکل معادل محاسبه یک رهبر است که یک کلاس هم ارز سلول های پیکربندی دوره ای است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
انتخاب رهبران در اتوماتای ​​سلولی دوره ای دو بعدی
چکیده انگلیسی
This article explores the computational power of bi-dimensional cellular automata acting on periodical configurations. It extends in some sense the results of a similar paper dedicated to the one-dimensional case. More precisely, we present an algorithm that computes a “minimal pattern network”, i.e. a minimal pattern and the two translation vectors it can use to tile the entire configuration. This problem is equivalent to the computation of a leader, which is one equivalence class of the cells of the periodical configuration.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 659, 10 January 2017, Pages 36-52
نویسندگان
,