×
Culik, Karel II

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

Inf. Process. Lett. 30, No. 3, 153-157 (1989).
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.

Cited in 20 Documents

MSC:

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

Keywords:

cellular automata; trellis language; firing squad problem; one-way cellular arrays; real-time

Citations:

Zbl 0646.68070
PDF BibTeX XML Cite
\textit{K. Culik II}, Inf. Process. Lett. 30, No. 3, 153--157 (1989; Zbl 0665.68043)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

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.