Variations of the firing squad problem and applications
From MaRDI portal
We give minimal time solutions for a few modifications of he firing squad problem. As an application we disprove a conjecture by \textit{O. H. Ibarra} and \textit{T. Jiang} [SIAM J. Comput. 16, 1135-1154 (1987; Zbl 0646.68070)] that proposes a candidate for showing that the class of languages accepted in real-time by one-way cellular arrays (OCA) is not closed under concentration. We show that their candidate and also similar languages are accepted by OCA in real-time.
Recommendations
Cites work
- A generalized firing squad problem
- An optimum solution to the firing squad synchronization problem
- scientific article; zbMATH DE number 3237733 (Why is no real title available?)
- On One-Way Cellular Arrays
- On real-time cellular automata and trellis automata
- Systolic trellis automatat†
- Topological transformations as a tool in the design of systolic networks
Cited in
(26)- An efficient solution of the firing mob problem
- The synchronization of nonuniform networks of finite automata
- Signals in one-dimensional cellular automata
- Language not recognizable in real time by one-way cellular automata
- Smaller solutions for the firing squad
- Language equations
- On hardest languages for one-dimensional cellular automata
- Abstract geometrical computation. 11: Slanted firing squad synchronisation on signal machines
- The minimum firing time of the generalized firing squad synchronization problem for squares
- The firing squad synchronization problem with sub-generals
- Recognition of poly-slender context-free languages by trellis automata
- A compositional approach to synchronize two-dimensional networks of processors
- Minimum and non-minimum time solutions to the firing squad synchronization problem
- Different time solutions for the firing squad synchronization problem on basic grid networks
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- The Distributed Firing Squad Problem
- Synchronization of 1-way connected processors
- Real time recognition with cellular automata : a meaningful example
- The firing squad synchronization problem on Cayley graphs
- Bounding the firing synchronization problem on a ring
- Revisiting the cutting of the firing squad synchronization
- Inductive definitions in logic versus programs of real-time cellular automata
- On hardest languages for one-dimensional cellular automata
- On real time one-way cellular array
- Closure properties of cellular automata
- Low complexity classes of multidimensional cellular automata
This page was built for publication: Variations of the firing squad problem and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116339)
