The Firing Squad Synchronization Problem (FSSP) is an old problem in theoretical Computer Science concerned with the synchronization of identical automata on lines of arbitrary length. Recent work by Umeo and Yanagihara explored partial solutions for the FSSP, where the original problem is relaxed to require synchronization only for some infinite proper subset of lengths. Umeo, Kamikawa and Yunès (UKY) investigated ring partial solutions, and found, via exhaustive testing of automata on a small number of lengths, that there are at most 17 4-state, symmetric candidate partial solutions for power-of-2 lengths greater than 1 (powers-of-2 solutions). They similarly tested and surmised the non-existence of 3-state ring partial solutions. This thesis extends UKY's work on rings as follows.
First, we devise a search procedure for partial solutions that backtracks on repeated configurations. We apply it to show that there are at most 97 candidate powers-of-2 solutions, 17 of which are UKY's symmetric ones, and 80 are new asymmetric ones. From this result we infer the non-existence of 4-state ring full solutions.
Second, we prove the powers-of-2 candidate solutions by introducing exponential rulesets, which are rulesets parameterized by exponents. We devise a procedure to generate exponential rulesets from an underlying ruleset. We apply this procedure to the candidate solutions to obtain a small, common set of exponential rulesets, which are then used to prove the candidate solutions.
Third, we devise a backtracking search procedure for firing exponential rulesets, i.e., exponential rulesets that synchronize. We use it to discover numerous firing exponential rulesets, effectively finding ring partial solutions for the FSSP generalized to nullities other than 2.
Last, we use de Bruijn subgraphs of ruleset minimal segments to prove the non-existence of 3-state ring partial solutions. We also provide an alternate computer-aided proof using firing transition graphs. These proofs suggest that graph-theoretic methods can be good starting points for resolving less tractable FSSP impossibility results.
An underlying theme of this thesis is the use of algorithmic techniques in formulating proofs of FSSP results. Our work shows that a judicious mix of analytic and computational methods is an effective way to approach the FSSP.
|Advisor:||Hayes, Wayne B.|
|Commitee:||Arvo, James R., Enciso, German A.|
|School:||University of California, Irvine|
|Department:||Information and Computer Science - Ph.D.|
|School Location:||United States -- California|
|Source:||DAI-B 73/01, Dissertation Abstracts International|
|Keywords:||Automata, Firing, Firing squad synchronization, Fssp, Rings, Synchronization problem|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be