کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874285 | 686507 | 2014 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The firing squad synchronization problem with sub-generals
ترجمه فارسی عنوان
مشکل همگام سازی شات با ژنرال ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، مشکل همگام سازی سوزش شات، خودکار سلولی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Firing Squad Synchronization Problem (FSSP), one of the most well-known problems related to cellular automata, was originally proposed by Myhill in 1957 and became famous through the work of Moore. The first solution to this problem was given by Minsky and McCarthy, and a minimal time solution was given by Goto. A considerable amount of research has also dealt with variants of this problem. In this paper, we introduce a new state called the sub-general to the original problem and propose the FSSP with sub-generals. In particular, we consider the case of one sub-general and determine the position of the sub-general in the array that minimizes the synchronization time. Moreover, we determine the minimal time to solve this problem and show that there exists no minimal time solution for any length of array. However, we show that the total time of our algorithm approaches arbitrarily close to the minimal time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issues 1â2, JanuaryâFebruary 2014, Pages 60-65
Journal: Information Processing Letters - Volume 114, Issues 1â2, JanuaryâFebruary 2014, Pages 60-65
نویسندگان
Kazuya Yamashita, Yasuaki Nishitani, Sadaki Hirose, Satoshi Okawa, Nobuyasu Osato,