Variations of the firing squad problem and applications (Q1116339): Difference between revisions
From MaRDI portal
Latest revision as of 13:16, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Variations of the firing squad problem and applications |
scientific article |
Statements
Variations of the firing squad problem and applications (English)
0 references
1989
0 references
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.
0 references
cellular automata
0 references
trellis language
0 references
firing squad problem
0 references
one-way cellular arrays
0 references
real-time
0 references