The Firing Squad Synchronization Problem (FSSP) is one of the best-studied problems for Cellular Automata (CA) and is part of many more sophisticated algorithms. Solutions for it such as the one from Mazoyer or Gerken use travelling signals, a basic technique of CA algorithms. Hence in addition to their importance, they represent typical CA algorithms. Beside the interest in their bandwidth following the definition of [1] they also serve well to study the methods for determining the bandwidth in the first place. As was demonstrated, bandwidth calculation for CA is a complex problem and requires the development of sophisticated algorithms. New approaches in this direction are given and compared using selected FSSP algorithms.
[1] Döring, A.: Bandwidth in cellular automata. PARS-Mitteilungen (2005) 118–125
Keywords: Doring, Doering
By: A. Döring
Published in: Proc. PARS Workshop 2010, in "Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware,", Germany, Ges. f. Informatik e.V., vol.24, p.176-184 in 2007
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .