Bounded Languages Meet Cellular Automata with Sparse Communication

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

10.4204/EPTCS.3.15

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Bounded Languages Meet Cellular Automata with Sparse Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounded Languages Meet Cellular Automata with Sparse Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded Languages Meet Cellular Automata with Sparse Communication will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-521673

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.