2D cellular automata: dynamics and undecidability

Details 2D cellular automata: dynamics and undecidability 2D cellular automata: dynamics and undecidability

2009-06-04

arxiv.org/abs/0906.0857v2

Computer Science

Formal Languages and Automata Theory

24 pages, 12 figures. paper submitted to an international conference

Scientific paper

In this paper we introduce the notion of quasi-expansivity for 2D CA and we show that it shares many properties with expansivity (that holds only for 1D CA). Similarly, we introduce the notions of quasi-sensitivity and prove that the classical dichotomy theorem holds in this new setting. Moreover, we show a tight relation between closingness and openness for 2D CA. Finally, the undecidability of closingness property for 2D CA is proved.

Affiliated with

Also associated with

No associations

Rating

2D cellular automata: dynamics and undecidability 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 2D cellular automata: dynamics and undecidability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 2D cellular automata: dynamics and undecidability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-494490