Cellular automata are one-dimensional arrays of interconnected
interacting finite automata. We investigate one of the
weakest classes, the real-time one-way cellular
automata, and impose an additional restriction on their
inter-cell communication by bounding the number
of allowed uses of the links between cells. Moreover,
we consider the devices as acceptors for bounded
languages in order to explore the borderline at which
non-trivial decidability problems of cellular automata classes
become decidable. It is shown that even devices with drastically
reduced communication, that is, each two neighboring cells may
communicate only constantly often, accept bounded languages that
are not semilinear. If the number of communications is
at least logarithmic in the length of the input, several
problems are undecidable. The same result is obtained for
classes where the total number of communications during a computation
is linearly bounded. |