کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426269 | 686021 | 2008 | 10 صفحه PDF | دانلود رایگان |
We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. We study whether for a given real-time CA working on finite configurations with fixed boundary conditions there exists a reverse real-time CA with the same neighborhood. It is shown that real-time reversibility is undecidable, which contrasts the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the undecidability of emptiness, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freedom. First steps towards the exploration of the computational capacity are done and closure under Boolean operations is shown.
Journal: Information and Computation - Volume 206, Issues 9–10, September–October 2008, Pages 1142-1151