Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/springer-journals/advances-in-unconventional-computing-a-class-of-non-optimum-time-fssp-wrP0ZKC0CQ
References (23)
-
H. Umeo, Masashi Maeda, Akihiro Sousa, Kiyohisa Taguchi (2015)
A Class of Non-optimum-time 3n-Step FSSP Algorithms - A Survey -
H. Umeo, N. Kamikawa, Jean-Baptiste Yunès (2009)
A Family of Smallest Symmetrical Four-State Firing Squad Synchronization Protocols for Ring ArraysParallel Process. Lett., 19
-
R. Vollmar (1982)
Some remarks about the “efficiency” of polyautomataInternational Journal of Theoretical Physics, 21
-
G. Herman (1971)
I. General description and the problem of universal computing abilityInternational Journal of Systems Science, 2
-
J. Mazoyer (1987)
A Six-State Minimal Time Solution to the Firing Squad Synchronization ProblemTheor. Comput. Sci., 50
-
Jean-Baptiste Yunès (2007)
Simple New Algorithms Which Solve the Firing Squad Synchronization Problem: A 7-States 4n-Steps Solution -
R. Balzer (1967)
An 8-state Minimal Time Solution to the Firing Squad Synchronization ProblemInf. Control., 10
-
G. Herman (1972)
Models for cellular interactions in development without polarity of individual cells II. Problems of synchronization and regulationInternational Journal of Systems Science, 3
-
P. Sanders (1994)
Massively Parallel Search for Transition-Tables of Polyautomata -
Y. Kobuchi (1987)
A Note on Symmetrical Cellular SpacesInf. Process. Lett., 25
-
H. Umeo, Jean-Baptiste Yunès, Takuya Yamawaki (2009)
A Simple Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays2009 International Conference on Computational Intelligence, Modelling and Simulation
-
H. Umeo, T. Yanagihara (2007)
A Smallest Five-State Solution to the Firing Squad Synchronization Problem -
Jean-Baptiste Yunès (2008)
A 4-states algebraic solution to linear cellular automata synchronizationInf. Process. Lett., 107
-
H. Umeo, Masashi Maeda, Kazuaki Hongyo (2006)
A Design of Symmetrical Six-State 3n-Step Firing Squad Synchronization Algorithms and Their Implementations -
A. Waksman (1966)
An Optimum Solution to the Firing Squad Synchronization ProblemInf. Control., 9
-
Jean-Baptiste Yunès (1994)
Seven-State Solutions to the Firing Squad Synchronization ProblemTheor. Comput. Sci., 127
-
H. Szwerinski (1986)
Symmetrical One-Dimensional Cellular SpacesInf. Control., 67
-
P. Fischer (1965)
Generation of Primes by a One-Dimensional Real-Time Iterative ArrayJ. ACM, 12
-
W. Hayes, W. Ng (2011)
Partial solutions for the firing squad synchronization problem on rings -
H. Umeo (2009)
Firing Squad Synchronization Problem in Cellular Automata -
E. Moore (1964)
The firing squad synchronization problem -
H. Umeo, Jean-Baptiste Yunès, N. Kamikawa, Juntarou Kurashiki (2009)
Small Non-Optimum-Time Firing Squad Synchronization Protocols for One-Dimensional Rings -
M. Minsky (1967)
Computation: Finite and Infinite Machines
- Publisher
- Springer International Publishing
- Copyright
- © Springer International Publishing Switzerland 2017
- ISBN
- 978-3-319-33923-8
- Pages
- 495 –521
- DOI
- 10.1007/978-3-319-33924-5_20
- Publisher site
- See Chapter on Publisher Site
Abstract
[Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata, known as the firing squad synchronization problem (FSSP), has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed. In the present chapter, we give a survey on a class of non-optimum-time 3n-step FSSP algorithms for synchronizing one-dimensional (1D) cellular automata of length n in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3n \pm O(\log n)$$\end{document} steps and present a comparative study of a relatively large-number of their implementations. We also propose two smallest-state, known at present, implementations of the 3n-step algorithm. This chapter gives the first complete transition rule sets implemented on finite state automata for the class of non-optimum-time 3n-step FSSP algorithms developed so far.]
Published: Jul 19, 2016
Keywords: Time Complexity; Internal State; Cellular Automaton; Transition Rule; Quiescent State