Variations of the firing squad problem and applications (Q1116339): Difference between revisions

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.