| Presentation | 1999/10/25 A Note on A. Waksman's Firing Squad Synchronization Algorithm Hiroshi Umeo, Yukihiro Nomura, Takashi Sogabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In 1966, A. Waksman proposed a 16-state firing squad synchronization algorithm, which is known, together with an unpublished Goto's algorithm, as the first-in-the-world optimum-time firing algorithm. Waksman described his algorithm in terms of the set of state transition tables, however, it has been reported in the talks of cellular automata researchers that some fatal errors were included in the Waksman's transition table. In this paper we correct all errors included in his transition table and give a complete simulation for any array less than 10000 cells. In our correction, ninety-three percent reduction has been made in the number of the original Waksman's transition rules. It has been shown that two-hundred and two rules are necessary and sufficient ones for the optimum-time firing squad synchronization. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Cellular Automaton / Firing Squad Synchronization Problem / Waksman's Firing Squad Synchronization Algorithm |
| Paper # | COMP99-46 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1999/10/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Note on A. Waksman's Firing Squad Synchronization Algorithm |
| Sub Title (in English) | |
| Keyword(1) | Cellular Automaton |
| Keyword(2) | Firing Squad Synchronization Problem |
| Keyword(3) | Waksman's Firing Squad Synchronization Algorithm |
| 1st Author's Name | Hiroshi Umeo |
| 1st Author's Affiliation | Osaka Electro-Communication Univ., Graduate School of Engineering, Faculty of Information Science and Technology() |
| 2nd Author's Name | Yukihiro Nomura |
| 2nd Author's Affiliation | Osaka Electro-Communication Univ., Graduate School of Engineering, Faculty of Information Science and Technology |
| 3rd Author's Name | Takashi Sogabe |
| 3rd Author's Affiliation | Osaka Electro-Communication Univ., Graduate School of Engineering, Faculty of Information Science and Technology |
| Date | 1999/10/25 |
| Paper # | COMP99-46 |
| Volume (vol) | vol.99 |
| Number (no) | 388 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |