The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le Problème de synchronisation des pelotons d'exécution (FSSP), l'un des problèmes les plus connus liés aux automates cellulaires, a été initialement proposé par Myhill en 1957 et est devenu célèbre grâce aux travaux de Moore [1]. La première solution à ce problème a été donnée par Minsky et McCarthy [2] et une solution en temps minimal a été donnée par Goto [3]. De nombreuses recherches ont également porté sur des variantes de ce problème. Dans cet article, d’un point de vue théorique, nous étendrons ce problème aux modèles numériques sur un affichage à sept segments. Certains de ces problèmes peuvent être généralisés comme FSSP pour certains arbres spéciaux appelés arbres de segments. Le FSSP pour les arbres de segments peut être réduit à un FSSP pour un tableau unidimensionnel divisé uniformément par des cellules jointes que nous appelons tableau de segments. Nous donnerons des algorithmes pour résoudre les FSSP pour ce tableau de segments et d'autres modèles numériques, respectivement. De plus, nous clarifierons le temps minimal nécessaire pour résoudre ces problèmes et montrerons qu’une telle solution n’existe pas.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Kazuya YAMASHITA, Mitsuru SAKAI, Sadaki HIROSE, Yasuaki NISHITANI, "The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 12, pp. 3276-3283, December 2010, doi: 10.1587/transinf.E93.D.3276.
Abstract: 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 [1]. The first solution to this problem was given by Minsky and McCarthy [2] and a minimal time solution was given by Goto [3]. A significant amount of research has also dealt with variants of this problem. In this paper, from a theoretical interest, we will extend this problem to number patterns on a seven-segment display. Some of these problems can be generalized as the FSSP for some special trees called segment trees. The FSSP for segment trees can be reduced to a FSSP for a one-dimensional array divided evenly by joint cells that we call segment array. We will give algorithms to solve the FSSPs for this segment array and other number patterns, respectively. Moreover, we will clarify the minimal time to solve these problems and show that there exists no such solution.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.3276/_p
Copier
@ARTICLE{e93-d_12_3276,
author={Kazuya YAMASHITA, Mitsuru SAKAI, Sadaki HIROSE, Yasuaki NISHITANI, },
journal={IEICE TRANSACTIONS on Information},
title={The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays},
year={2010},
volume={E93-D},
number={12},
pages={3276-3283},
abstract={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 [1]. The first solution to this problem was given by Minsky and McCarthy [2] and a minimal time solution was given by Goto [3]. A significant amount of research has also dealt with variants of this problem. In this paper, from a theoretical interest, we will extend this problem to number patterns on a seven-segment display. Some of these problems can be generalized as the FSSP for some special trees called segment trees. The FSSP for segment trees can be reduced to a FSSP for a one-dimensional array divided evenly by joint cells that we call segment array. We will give algorithms to solve the FSSPs for this segment array and other number patterns, respectively. Moreover, we will clarify the minimal time to solve these problems and show that there exists no such solution.},
keywords={},
doi={10.1587/transinf.E93.D.3276},
ISSN={1745-1361},
month={December},}
Copier
TY - JOUR
TI - The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays
T2 - IEICE TRANSACTIONS on Information
SP - 3276
EP - 3283
AU - Kazuya YAMASHITA
AU - Mitsuru SAKAI
AU - Sadaki HIROSE
AU - Yasuaki NISHITANI
PY - 2010
DO - 10.1587/transinf.E93.D.3276
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2010
AB - 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 [1]. The first solution to this problem was given by Minsky and McCarthy [2] and a minimal time solution was given by Goto [3]. A significant amount of research has also dealt with variants of this problem. In this paper, from a theoretical interest, we will extend this problem to number patterns on a seven-segment display. Some of these problems can be generalized as the FSSP for some special trees called segment trees. The FSSP for segment trees can be reduced to a FSSP for a one-dimensional array divided evenly by joint cells that we call segment array. We will give algorithms to solve the FSSPs for this segment array and other number patterns, respectively. Moreover, we will clarify the minimal time to solve these problems and show that there exists no such solution.
ER -