Variations of the firing squad problem and applications
type: Item
instance of: scholarly article
title: Variations of the firing squad problem and applications
zbMATH Open document ID: 0665.68043
DOI: 10.1016/0020-0190(89)90134-8
author: Karel II Culik
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4088937
zbMATH Keywords: cellular automata
zbMATH Keywords: trellis language
zbMATH Keywords: firing squad problem
zbMATH Keywords: one-way cellular arrays
zbMATH Keywords: real-time
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90134-8
OpenAlex ID: W2004637691
cites work: On real-time cellular automata and trellis automata
cites work: Topological transformations as a tool in the design of systolic networks
cites work: Systolic trellis automatat†
cites work: On One-Way Cellular Arrays
cites work: Q5525259
cites work: A generalized firing squad problem
cites work: An optimum solution to the firing squad synchronization problem
description: scientific article; zbMATH DE number 4088937