Skip to main content
SpringerLink
Log in
Book cover

Encyclopedia of Complexity and Systems Science pp 1–60Cite as

Cellular Automata, Firing Squad Synchronization Problem in

  • Living reference work entry
  • First Online:

  • 388 Accesses

Glossary

Cellular automaton (CA):

A cellular automaton (CA) is a discrete computational model studied in mathematics, computer science, economics, biology, physics, chemistry, etc. It consists of a regular array of cells, and each cell is a finite-state automaton. The array can be arranged in any finite number of dimensions. Time (step) is discrete, and the state of a cell at time t (≥1) is a function of the states of a finite number of cells (called its neighborhood) at time t − 1. Each cell has the same rule set for updating its next state, based on the states in the neighborhood. At every step the rules are applied to the whole array synchronously, yielding a new configuration.

Firing squad synchronization problem (FSSP):

The FSSP is stated as follows: given an array of n identical cellular automata, including a general on the left end which is activated at time t = 0, one wants to give the description (state set and next-state function) of the automata so that at some future time,...

This is a preview of subscription content, log in via an institution.

Bibliography

  • Balzer R (1967) An 8-state minimal time solution to the firing squad synchronization problem. Inf Control 10:22–42

    Article  MATH  Google Scholar 

  • Berthiaume A, Bittner T, Perković L, Settle A, Simon J (2004) Bounding the firing synchronization problem on a ring. Theor Comput Sci 320:213–228

    Article  MathSciNet  MATH  Google Scholar 

  • Beyer WT(1969) Recognition of topological invariants by iterative arrays. Ph.D. thesis, MIT, p 144

    Google Scholar 

  • Burns JE, Lynch NA (1987) The Byzantine firing squad problem. In: Advances in computing research: parallel and distributed computing, vol 4. JAI Press, pp 147–161

    Google Scholar 

  • Coan BA, Dolev D, Dwork C, Stockmeyer L (1989) The distributed firing squad problem. SIAM J Comput 18(5):990–1012

    Article  MathSciNet  MATH  Google Scholar 

  • Culik K II (1989) Variations of the firing squad synchronization problem and applications. Inf Process Lett 30:153–157

    Article  MATH  Google Scholar 

  • Culik K II, Dube S (1991) An efficient solution of the firing mob problem. Theor Comput Sci 91:57–69

    Article  MathSciNet  MATH  Google Scholar 

  • Fischer PC (1965) Generation of primes by a one-dimensional real-time iterative array. J ACM 12(3):388–394

    Article  MathSciNet  MATH  Google Scholar 

  • Gerken H-D (1987) Über Synchronisations – Probleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, p 50

    Google Scholar 

  • Goldstein D, Kobayashi K (2004) On the complexity of network synchronization. Proc ISSAC 2004, LNCS 3341:496–507

    MathSciNet  MATH  Google Scholar 

  • Goldstein D, Meyer N (2002) The wake up and report problem is asymptotically time-equivalent to the firing squad synchronization problem. In: Proceedings of 13th annual ACM-SIAM symposium on discrete algorithms, New York, pp 578–587

    Google Scholar 

  • Goto E (1962) A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics, vol 298. Harvard University, pp 52–59, with an illustration in color

    Google Scholar 

  • Goto E (1966) Some puzzles on automata. In: Kitagawa T (ed) Toward computer sciences, Kyouritsu, pp 67–91 (in Japanease)

    Google Scholar 

  • Grasselli A (1975) Synchronization of cellular arrays: the firing squad problem in two dimensions. Inf Control 28:113–124

    Article  MathSciNet  MATH  Google Scholar 

  • Grefenstette JJ (1983) Network structure and the firing squad synchronization problem. J Comput Syst Sci 26:139–152

    Article  MathSciNet  MATH  Google Scholar 

  • Grigorieff S (2006) Synchronization of a bounded degree graph of cellular automata with non uniform delays in time Δ⌊log m (δ)⌋. Theor Comput Sci 356(1):170–185

    Article  MathSciNet  MATH  Google Scholar 

  • Gruska J, Torre SL, Parente M (2007) The firing squad synchronization problem on squares, toruses and rings. Int J Found Comput Sci 18(3):637–654

    Article  MathSciNet  MATH  Google Scholar 

  • Herman GT (1971) Models for cellular interactions in development without polarity of individual cells. I General description and the problem of universal computing ability. Int J Syst Sci 2(3):271–289

    Article  MATH  Google Scholar 

  • Herman GT (1972) Models for cellular interactions in development without polarity of individual cells. II. Problems of synchronization and regulation. Int J Syst Sci 3(2):149–175

    Article  MATH  Google Scholar 

  • Herman GT, Liu WH, Rowland S, Walker A (1974) Synchronization of growing cellular systems. Inf Control 25:103–122

    Article  MATH  Google Scholar 

  • Imai K, Morita K (1996) Firing squad synchronization problem in reversible cellular automata. Theor Comput Sci 165:475–482

    Article  MathSciNet  MATH  Google Scholar 

  • Jiang T (1992) The synchronization of nonuniform networks of finite automata. Inf Comput 97:234–261

    Article  MathSciNet  MATH  Google Scholar 

  • Kobayashi K (1977) The firing squad synchronization problem for two-dimensional arrays. Inf Control 34:177–197

    Article  MathSciNet  MATH  Google Scholar 

  • Kutrib M, Vollmar R (1991) Minimal time synchronization in restricted defective cellular automata. J Inform Process Cybern., ELK 27:179–196

    MATH  Google Scholar 

  • Kutrib M, Vollmar R (1995) The firing squad synchronization problem in defective cellular automata. IEICE Trans Inf and Syst E78-D(7):895–900

    Google Scholar 

  • Maignan L Yunès J-B (2012) A spatio-temporal algorithmic point of view on firing squad synchronisation problem. ACRI 2012, LNCS 7495, pp 101–110

    Google Scholar 

  • Maignan L, Yunès J-B (2014a) Synchronizing the squad with (almost) arbitrary cut ratio. CANDAR 2016a: 229–235

    Google Scholar 

  • Maignan L, Yunès J-B (2014b) Experimental finitization of infinite field-based generalized FSSP solution. ACRI 2014, LNCS 8751:136–145

    Google Scholar 

  • Maignan L, Yunès J-B (2014c) Generalized FSSP on hexagonal tiling: towards arbitrary regular spaces. Automata:83–96

    Google Scholar 

  • Maignan L, Yunès J-B (2016a) Finitization of infinite field-based multi-general FSSP solution. J Cell Autom 12(1–2):121–139

    MathSciNet  Google Scholar 

  • Maignan L, Yunès J-B (2016b) A field based solution of Mazoyer’s FSSP schema. ACRI 2016, LNCS 9863:134–143

    Google Scholar 

  • Manzoni L, Umeo H (2014) The firing squad synchronization problem with multiple updating cycles. Theor Comput Sci 559:108–117

    Article  MathSciNet  MATH  Google Scholar 

  • Mazoyer J (1986) An overview of the firing squad synchronization problem, Lecture notes on computer science, vol 316. Springer, pp 82–93

    Google Scholar 

  • Mazoyer J (1987) A six-state minimal time solution to the firing squad synchronization problem. Theor Comput Sci 50:183–238

    Article  MathSciNet  MATH  Google Scholar 

  • Mazoyer J (1996) On optimal solutions to the firing squad synchronization problem. Theor Comput Sci 168:367–404

    Article  MathSciNet  MATH  Google Scholar 

  • Mazoyer J (1997) A minimal-time solution to the FSSP without recursive call to itself and with bounded slope of signals. Draft version, p 8

    Google Scholar 

  • Mazoyer J (2013) Synchronization of growing lines of automata. Draft

    Google Scholar 

  • Mazoyer J, Yunès J-B (2012) Computations on cellular automata. Handb Natur Comput:159–188

    Google Scholar 

  • Minsky M (1967) Computation: finite and infinite machines. Prentice Hall, pp 28–29

    Google Scholar 

  • Moore EF (1964) The firing squad synchronization problem. In: Moore EF (ed) Sequential machines, selected papers. Addison-Wesley, Reading, pp 213–214

    Google Scholar 

  • Moore FR, Langdon GG (1968) A generalized firing squad problem. Inf Control 12:212–220

    Article  MATH  Google Scholar 

  • Ng WL (2011) Partial solutions for the firing squad synchronization problem on rings. ProQuest publications, Ann Arbor, pp 1–363

    Google Scholar 

  • Nguyen HB, Hamacher VC (1974) Pattern synchronization in two-dimensional cellular space. Inf Control 26:12–23

    Article  MathSciNet  MATH  Google Scholar 

  • Nishimura J Umeo H (2005) An optimum-time synchronization protocol for 1-bit-communication cellular automaton. In: Proceedings of the 9th world multi-conference on systemics, cybernetics and informatics, vol 10, Orlando, Florida, pp 232–237

    Google Scholar 

  • Nishitani Y, Honda N (1981) The firing squad synchronization problem. Theor Comput Sci 14:39–61

    Article  MathSciNet  MATH  Google Scholar 

  • Noguchi K (2004) Simple 8-state minimal time solution to the firing squad synchronization problem. Theor Comput Sci 314:303–334

    Article  MathSciNet  MATH  Google Scholar 

  • Roka Z (1995) The firing squad synchronization problem on Cayley graphs. MFCS’95, LNCS 969, pp 402–411

    Google Scholar 

  • Romani F (1976) Cellular automata synchronization. Inf Sci 10:299–318

    Article  MATH  Google Scholar 

  • Romani F (1977) On the fast synchronization of tree connected networks. Inf Sci 12:229–244

    Article  MathSciNet  MATH  Google Scholar 

  • Romani F (1978) The parallelism principle: speeding up the cellular automata synchronization. Inf Control 36:245–255

    Article  MathSciNet  MATH  Google Scholar 

  • Rosenstiehl P, Fiksel JR, Holliger A (1972) Intelligent graphs: networks of finite automata capable of solving graph problems. In: Graph theory and computing. Academic, New York, pp 219–265

    Google Scholar 

  • Sanders P (1994) Massively parallel search for transition-tables of polyautomata. In: Jesshope C, Jossifov V, Wilhelmi W (eds) Proceedings of the VI international workshop on parallel processing by cellular automata and arrays, Akademie, pp 99–108

    Google Scholar 

  • Schmid H Worsch T (2004) The firing squad synchronization problem with many generals for one-dimensional CA. In: Proceedings of IFIP world congress, pp 111–124

    Google Scholar 

  • Settle A Simon J (1998) Improved bounds for the firing synchronization problem. In: SIROCCO 5: proceedings of the 5th international colloquium on structural information and communication complexity, Carleton Scientific, pp 66–81

    Google Scholar 

  • Settle A, Simon J (2002) Smaller solutions for the firing squad. Theor Comput Sci 276:83–109

    Article  MathSciNet  MATH  Google Scholar 

  • Shinahr I (1974) Two- and three-dimensional firing squad synchronization problems. Inf Control 24:163–180

    Article  MathSciNet  MATH  Google Scholar 

  • Szwerinski H (1982) Time-optimum solution of the firing-squad-synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theor Comput Sci 19:305–320

    Article  MathSciNet  MATH  Google Scholar 

  • Torre SL, Napoli M, Parente D (1996) Synchronization of one-way connected processors. Complex Syst 10:239–255

    MathSciNet  MATH  Google Scholar 

  • Torre SL, Napoli M, Parente D (1998) Synchronization of a line of identical processors at a given time. Fundam Inform 34:103–128

    MathSciNet  MATH  Google Scholar 

  • Torre SL, Napoli M, Parente M (2000) A compositional approach to synchronize two dimensional networks of processors. Theore Inform Appl 34:549–564

    Article  MathSciNet  MATH  Google Scholar 

  • Torre SL, Napoli M Parente M (2001) Firing squad synchronization problem on bidimensional cellular automata with communication constraints. In: Proceedings of MCU 2001, LNCS 2055, pp 264–275

    Google Scholar 

  • Umeo H (1996) A note on firing squad synchronization algorithms-A reconstruction of Goto’s first-in-the-world optimum-time firing squad synchronization algorithm. In: Kutrib M, Worsch T (eds) Proceedings of cellular automata workshop, Giessen, Germany, p 65

    Google Scholar 

  • Umeo H (2001) Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton. Parallel Comput 27:587–599

    Article  MathSciNet  MATH  Google Scholar 

  • Umeo H (2004) A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE Trans Inf Syst E87-D(3):733–739. 2004

    Google Scholar 

  • Umeo H (2008) Firing squad synchronization algorithms for two-dimensional cellular automata. J Cell Autom 4:1–20

    MathSciNet  MATH  Google Scholar 

  • Umeo H (2009) Firing squad synchronization problem in cellular automata. In: Meyers RA (ed) Encyclopedia of complexity and system science, vol 4. Springer, Heidelberg, pp 3537–3574

    Chapter  Google Scholar 

  • Umeo H (2010) Problem solving on one-bit-communication cellular automata. In: Hoekstra AG et al (eds) Simulating complex systems by cellular automata. Springer, Berlin, pp 117–144

    Chapter  Google Scholar 

  • Umeo H (2011) Recent developments in firing squad synchronization algorithms for two-dimensional cellular automata and their state-efficient implementations. In: Proceedings of 13rd international conference on automata and formal languages, AFL 2011, Debrecen, Hungary, pp 368–387

    Google Scholar 

  • Umeo H (2012) Synchronizing square arrays in optimum-time. Int J Gen Syst 41(6):617–631

    Article  MathSciNet  MATH  Google Scholar 

  • Umeo H (2014a) FSSP algorithms for square and rectangular arrays. In: Modeling, simulation and optimization of complex processes, HPCS 2012. Springer, Switzerland, pp 245–259

    Google Scholar 

  • Umeo H (2014b) Time-optimum smaller-state synchronizers for cellular automata. In: Computing with new resources, LNCS 8808. Springer, Cham, pp 129–145

    Google Scholar 

  • Umeo H (2016a) Small synchronizers and prime generators. In: Designing beauty: the art of cellular automata. Emergence, complexity and computation, vol 20. Springer, Cham, pp 87–95

    Google Scholar 

  • Umeo H (2016b) A class of non-optimum-time FSSP algorithms. In: Advances in unconventional computing, vol 1. Theory, Emergence, complexity and computation, ECC 22, Springer, Cham, pp 495–521

    Google Scholar 

  • Umeo H (2017) Synchronization algorithms for 2D rectangular arrays – recent developments –. In: Adamatzky A (ed) Reversible computing. Springer, Switzerland, (to appear)

    Google Scholar 

  • Umeo H, Imai K (2016) A class of minimum-time minimum-state-change generalized FSSP algorithms. In: El Yacoubi S et al (eds) Proceedings of ACRI 2016, LNCS 9863. Springer International Publishing, Cham, pp 1–11

    Google Scholar 

  • Umeo H, Kamikawa N (2003) Real-time generation of primes by a 1-bit-communication cellular cutomaton. Fundam Inform 58:421–435

    MATH  Google Scholar 

  • Umeo H, Kamikawa N A (2017) new class of smallest four-state FSSP partial solutions for one-dimensional cellular automata. Proceedings of PaCT 2017, LNCS 10421, Springer International Publishing, pp 232–245

    Google Scholar 

  • Umeo H, Kubo K (2010) A seven-state time-optimum square synchronizer. In: Proceedings of international conference on cellular automata for research and industry. ACRI 2010, LNCS 6350, pp 219–230

    Google Scholar 

  • Umeo H, Kubo K (2012) Recent developments in constructing square synchronizers. In: Proceedings of 10th international conference on cellular automata for research and industry. ACRI 2012, LNCS 7495, pp 171–183

    Google Scholar 

  • Umeo H, Kubo K (2015) An FSSP on torus. In: Proceedings of the 2015 international symposium on computing and networking. IEEE CPS, New York, pp 453–456

    Google Scholar 

  • Umeo H, Uchino H (2008) A new time-optimum synchronization algorithm for rectangle arrays. Fundam Inform 87(2):155–164

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Yanagihara T (2007) A smallest five-state solution to the firing squad synchronization problem. In: Proc. of 5th intern. conf. on machines, computations, and universality. MCU 2007, LNCS 4664, pp 292–302

    Google Scholar 

  • Umeo H, Yanagihara T (2009) A small five-state non-optimum-time solution to the firing squad synchronization problem – a geometrical approach. Fundam Inform 91:161–178. 2009

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Yanagihara T (2011) Smallest implementation of optimum-time firing squad synchronization algorithms for one-bit-communication cellular automata. In: Proceedings of 11th intern. conf. on parallel computing and technologies. PaCT 2011, LNCS 6873, pp 210–223

    Google Scholar 

  • Umeo H, Sogabe T, Nomura Y (2000) Correction, optimization and verification of transition rule set for Waksman’s firing squad synchronization algorithm. In: Proceedings of the fourth international conference on cellular automata for research and industry. Springer, pp 152–160

    Google Scholar 

  • Umeo H, Hisaoka M, Michisaka K, Nishioka K, Maeda M (2002a) Some new generalized synchronization algorithms and their implementations for large scale cellular automata. In: Proceedings of the 3rd international conference on unconventional models of computation: UMC 2002. LNCS 2509, pp 276–286

    Google Scholar 

  • Umeo H, Maeda M Fujiwara N (2002b) An efficient mapping scheme for embedding any one-dimensional firing squad synchronization algorithm onto two-dimensional arrays. In: Proceedings of the 5th international conference on cellular automata for research and industry, LNCS 2493, Springer, pp 69–81

    Google Scholar 

  • Umeo H, Michisaka K, Kamikawa N (2003) A synchronization problem on 1-bit-communication cellular automata. In: Proceedings of international conference on computational science-ICCS2003, LNCS 2657, pp 492–500

    Google Scholar 

  • Umeo H, Hisaoka M, Akiguchi S (2005a) A twelve-state optimum-time synchronization algorithm for two-dimensional rectangular arrays. In: Proceedings of the 4th international conference on unconventional computation: UC 2005, LNCS 3699, pp 214–223

    Google Scholar 

  • Umeo H, Hisaoka M, Teraoka M Maeda M (2005b) Several new generalized linear- and optimum-time synchronization algorithms for two-dimensional rectangular arrays. In: Margenstern M (ed), Proceedings of the 4th international conference on machines, computations and universality: MCU 2004, LNCS 3354, pp 223–232

    Google Scholar 

  • Umeo H, Hisaoka M, Sogabe T (2005c) A survey on optimum-time firing squad synchronization algorithms for one-dimensional cellular automata. Int J Unconv Comput 1:403–426

    MATH  Google Scholar 

  • Umeo H, Yanagihara T, Kanazawa M (2006a) State-efficient firing squad synchronization protocols for communication-restricted cellular automata. In: Proceedings of 7th international conference on cellular automata for research and industry. ACRI2006, LNCS 4173, pp 169–181

    Google Scholar 

  • Umeo H, Maeda M, Hisaoka M, Teraoka M (2006b) A state-efficient mapping scheme for designing two-dimensional firing squad synchronization algorithms. Fundam Informat 74(4):603–623

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Maeda M, Hongyo K (2006c) A design of symmetrical six-state 3n-step firing squad synchronization algorithms and their implementations. In: Proceedings of 7th international conference on cellular automata for research and industry. ACRI2006, LNCS 4173, pp 157–168

    Google Scholar 

  • Umeo H, Yamawaki T, Shimizu N, Uchino H (2007a) Modeling and simulation of global synchronization processes for large-scale-of two-dimensional cellular arrays. In: Proceedings of international conference on modeling and simulation. AMS 2007, New York, pp 139–144

    Google Scholar 

  • Umeo H, Kamikawa N Yunès JB (2007b) A four-state solution to the firing squad synchronization problem based on Wolfram’s rule 150 (in preparation)

    Google Scholar 

  • Umeo H, Michisaka K, Kamikawa N, Kanazawa M (2007c) State-efficient one-bit-communication solutions for some classical cellular automata problems. Fundam Informat 78:449–465

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Kamikawa N, Yunès J-B (2009) A family of smallest symmetrical four-state firing squad synchronization protocols for ring arrays. Parallel Process Lett 19:299–313

    Article  MathSciNet  Google Scholar 

  • Umeo H, Kamikawa N, Nishioka K, Akiguchi S (2010) Generalized firing squad synchronization protocols for one-dimensional cellular automata – a survey. Acta Physica Polonica B Proc Suppl 3:267–289

    Google Scholar 

  • Umeo H, Uchino H, Nomura A (2011a) How to synchronize square arrays in optimum-time – A new square synchronization algorithm –. In: Proceeings of the 2011 international conference on high performance computing and simulation. HPCS 2011, IEEE, New York, pp 801–807

    Google Scholar 

  • Umeo H, Nishide K, Yamawaki T (2011b) A new optimum-time firing squad synchronization algorithm for two-dimensional rectangle arrays: one-sided recursive-halving based. In: 7th conference on computability in Europe. LNCS 6735, pp 290–299

    Google Scholar 

  • Umeo H, Nishide K, Kubo K (2012a) A simple optimum-time FSSP algorithm for multi-dimensional cellular automata. DCM: 151–165

    Google Scholar 

  • Umeo H, Yamawaki T, Nishide K (2012b) A new optimum-time firing squad synchronization algorithm for two-dimensional rectangle arrays – freezing-thawing technique based. J Cell Autom 7:31–46

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Uchino H, Nomura A (2013) An optimum-time square synchronization algorithm. J Cell Autom 8:39–51

    MathSciNet  MATH  Google Scholar 

  • Umeo H, Imai K, Sousa A(2015a) A generalized minimum-time minimum-state-change FSSP algorithm. In: Proceedimhs of the 4th international conference on the theory and practise of natural computing. TPNC 2015, LNCS 9477. Springer International Publishing, Switzerland, pp 161–173

    Google Scholar 

  • Umeo H, Maeda M, Sousa A, Taguchi K (2015b) A class of non-optimum-time 3n–step FSSP algorithms –a survey –. In: Proceedings of 13th international conference on parallel computing and technologies. PaCT 2015, LNCS 9251, pp 231–245

    Google Scholar 

  • Umeo H, Miyamoto K, Abe Y (2015c) Real-time prime generators implemented on small-state cellular automata. In: Adamatzky A (ed) Automata, universality, computation. Springer, Cham, pp 341–352

    Google Scholar 

  • Umeo H, Kubo K, Nishide K (2015d) A class of FSSP algorithms for multi-dimensional cellular arrays. Commun Nonlinear Sci Numer Simul 21:200–209

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Umeo H, Hirota M, Nozaki Y, Imai K, Sogabe T (2017a) A new reconstruction and the first implementation of Goto’s FSSP algorithm. Appl Math Comput 1–31. https://doi.org/10.1016/J.amc.2017.05.015

  • Umeo H, Imai K, Sousa A (2017b) A design of generalized minimum-state-change FSSP algorithms. Nat Comput 1–20. https://doi.org/10.1607/s11047-017-9625-2

  • Varshavsky VI, Marakhovsky VB, Peschansky VA (1970) Synchronization of interacting automata. Math Syst Theory 4(3):212–230

    Article  MathSciNet  Google Scholar 

  • Vivien H (2005) Cellular automata: a geometrical approach. Draft, p 412

    Google Scholar 

  • Vollmar R (1979) Algorithmen in Zellularautomaten, Teubner, p 192

    Google Scholar 

  • Vollmar R (1982) Some remarks about the “Efficiency” of polyautomata. Int J Theor Phys 21(12):1007–1015

    Article  MathSciNet  MATH  Google Scholar 

  • Waksman A (1966) An optimum solution to the firing squad synchronization problem. Inf Control 9(1966):66–78

    Article  MathSciNet  MATH  Google Scholar 

  • Yunès JB (1994) Seven-state solution to the firing squad synchronization problem. Theor Comput Sci 127:313–332

    Article  MathSciNet  MATH  Google Scholar 

  • Yunès JB (2006) Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata. J Cell Autom 1:253–268

    MathSciNet  MATH  Google Scholar 

  • Yunès JB (2007) Simple new algorithms which solve the firing squad synchronization problem: A 7-states 4n-steps solution. In: Proceeings of 5th international conference on machines, computations, and universality. MCU 2007, LNCS 4664, pp 316–324

    Google Scholar 

  • Yunès JB (2008a) An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem. Theor Inform Appl 42(1), 55–68

    Google Scholar 

  • Yunès JB (2008b) A 4-states algebraic solution to linear cellular automata synchronization. Inf Process Lett 19(2):71–75

    Article  MATH  Google Scholar 

  • Yunès J-B (2008c) Goto’s construction and Pascal’s triangle: new insights into cellular automata synchronization. Proc JAC 2008:195–203

    Google Scholar 

  • Yunès J-B (2009) Known CA synchronizers made insensitive to the initial state of the initiato. J Cell Autom 4(2):147–158

    MathSciNet  MATH  Google Scholar 

  • Yunès J-B, Maignan L (2013) Moore and von Neumann neighborhood n-dimensional generalized firing squad solutions using fields. CANDAR:552–558

    Google Scholar 

Books and Reviews

  • Delorme M, Mozoyer J (1999) Cellular automata. Kluwer Academic Publishers, p 373

    Google Scholar 

  • Ilachinski A (2001) Cellular automata – a discrete universe. World Scientific, p 808

    Google Scholar 

  • Wolfram S (1994) Cellular automata and complexity. Addison-Wesley Publishing Company, p 596

    Google Scholar 

  • Wolfram S (2002) A new kind of science. Wolfram Media, p 1280

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho 18-8, 572-8530, Osaka, Japan

    Hiroshi Umeo

Authors
  1. Hiroshi Umeo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hiroshi Umeo .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer Science+Business Media LLC

About this entry

Cite this entry

Umeo, H. (2017). Cellular Automata, Firing Squad Synchronization Problem in. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27737-5_211-4

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27737-5_211-4

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-27737-5

  • Online ISBN: 978-3-642-27737-5

  • eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics

Publish with us

Policies and ethics

Search

Navigation