Affordable Access

Publisher Website

A tight linear bound on the synchronization delay of bijective automata

Theoretical Computer Science
Publication Date
DOI: 10.1016/j.tcs.2007.02.052
  • Reversible Cellular Automata
  • Inverse Neighborhood
  • Local Automata
  • Synchronization Delay


Abstract Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. We generalize these systems by introducing the class of ω ω bijective finite automata. It consists of those finite automata where for any bi-infinite word there exists a unique path labelled by that word. These systems are strictly included in the class of local automata. Although the synchronization delay of an n -state local automaton is known to be Θ ( n 2 ) in the worst case, we prove that in the case of ω ω bijective finite automata the synchronization delay is at most n − 1 . Based on this we prove that for a one-dimensional n -state RCA where the neighborhood consists of m consecutive cells, the neighbourhood of the inverse automaton consists of at most n m − 1 − ( m − 1 ) cells. Similar bounds are obtained also in [E. Czeizler, J. Kari, A tight linear bound on the neighborhood of inverse cellular automata, in: Proceedings of ICALP 2005, in: LNCS, vol. 3580, 2005, pp. 410–420] but here the result comes as a direct consequence of the more general result. We also construct examples of RCA with large inverse neighbourhoods proving that the upper bounds provided here are the best possible in the case m = 2 .

There are no comments yet on this publication. Be the first to share your thoughts.