The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 2010-12-01

著者

• Hirose Sadaki

  Faculty Of Engineering Toyama University

• Sakai Mitsuru

  Faculty Of Engineering University Of Toyama

• Nishitani Yasuaki

  Faculty Of Engineering Iwate University

• Nishitani Yasuaki

  Faculty Of Engineering Gunma University

• Yamashita Kazuya

  Faculty Of Engineering University Of Toyama

関連論文

• Control Methods of Genetic Algorithms under Changing Environments
• High Speed Hypothetical Reasoning System with Case-Based Reasoning for Diagnosing Faults
• Some Relations between Watson-Crick Finite Automata and Chomsky Hierarchy(Automata and Formal Language Theory)
• On Computational Power of Insertion-Deletion Systems without Using Contexts(Automata and Formal Language Theory)
• A Faster Algorithm of Minimizing AND-EXOR Expressions
• The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays
• The Relations among Watson-Crick Automata and Their Relations with Context-Free Languages(Automata and Formal Language Theory)
• Double Fixed-Polarity Reed-Muller Expressions:A New Class of AND-EXOR Expressions for Compact and Testable Realization (特集 システムLSIの設計技術と設計自動化)
• Easily Testable Realization Based on Single-Rail-Input OR-AND-EXOR Expressions
• Minimization of AND-EXOR Expressions for Symmetric Functions (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
• Lower Bounds on Size of Periodic Functions in Exclusive-OR Sum-of-Products Expressions (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)
• Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem

もっと見る 閉じる

スポンサーリンク