×

Variations of the firing squad problem and applications. (English) Zbl 0665.68043

We give minimal time solutions for a few modifications of he firing squad problem. As an application we disprove a conjecture by O. H. Ibarra and 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.

MSC:

68Q80 Cellular automata (computational aspects)
68Q45 Formal languages and automata

Citations:

Zbl 0646.68070
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Choffrut, C.; Culik, K., On real-time cellular automata and Trellis automata, Acta informatica, 21, 393-407, (1984) · Zbl 0534.68039
[2] Culik, K.; Fris, I., Topological transformation as a tool in the design of systolic networks, Theoret. comput. sci., 37, 183-216, (1985) · Zbl 0584.68068
[3] Culik, K.; Gruska, J.; Salomaa, A., Systolic Trellis automata, Internat. J. comput. math., 16, 3-22, (1984), Part II · Zbl 0571.68042
[4] Culik, K.; Yu, Sheng, Translation of systolic algorithms between systems of different topology, Proc. 1985 IEEE & ACM international conference on parallel processing, 756-763, (1985)
[5] Dyer, C., One-way bounded cellular automata, Inf. control, 44, 54-69, (1980)
[6] Ibarra, O.H.; Jiang, T., On one-way cellular arrays, SIAM J. comput., 16, 1135-1154, (1987) · Zbl 0646.68070
[7] Moore, E.F., Sequential machines. selected papers, (), 213-214
[8] Moore, F.R.; Langdon, G.G., A generalized firing squad problem, Inf. and control, 12, 212-220, (1968) · Zbl 0157.02202
[9] Waksman, A., On optimum solution to the firing squad synchronization problem, Inf. and control, 9, 66-78, (1966) · Zbl 1111.68527
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.