A six-state minimal time solution to the Firing squad synchronization problem
type: Item
instance of: scholarly article
title: A six-state minimal time solution to the Firing squad synchronization problem
zbMATH Open document ID: 0635.68042
DOI: 10.1016/0304-3975(87)90124-1
author: B. George
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: The firing squad synchronization problem is the problem of synchronization of n finite state automata connected in the structure of a one-dimensional systolic array. The time-optimal solution with eight states was presented by \textit{R. Balzar} [An 8-states minimal time solution to the firing squad synchronization problem, Inf. Control 10, 22-42 (1967)]. Using a new method the author gives a new time-optimal solution with six states only. An open problem remains whether this number can be decreased to 5 (at least five states are necessary).
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4035143
zbMATH Keywords: one-dimensional cellular structure
zbMATH Keywords: minimization of the number of states
zbMATH Keywords: firing squad synchronization
zbMATH Keywords: finite state automata
zbMATH Keywords: systolic array
MaRDI profile type: Publication
Wikidata QID: Q29300723
full work available at URL: 0304-3975(87)90124-1
OpenAlex ID: W2108002652
cites work: An 8-state minimal time solution to the firing squad synchronization problem
cites work: Q5533191
cites work: An optimum solution to the firing squad synchronization problem
cites work: Q5590814
description: scientific article; zbMATH DE number 4035143