IEICE TRANSACTIONS on Information
The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E93-D No.12 pp.3276-3283
- Publication Date
- 2010/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E93.D.3276
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
