The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -