Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Tight Linear Bound on the Sy...

A Tight Linear Bound on the Synchronization Delay of Bijective Automata

Eugen Czeizler, Jarkko Kari, A Tight Linear Bound on the Synchronization Delay of Bijective Automata. Theoretical Computer Science 380(1-2), 23–36, 2007.

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 nm−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.

BibTeX entry:

@ARTICLE{jCzKa07a,
  title = {A Tight Linear Bound on the Synchronization Delay of Bijective Automata},
  author = {Czeizler, Eugen and Kari, Jarkko},
  journal = {Theoretical Computer Science},
  volume = {380},
  number = {1-2},
  pages = {23–36},
  year = {2007},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication