Non-deterministic cellular automata and languages

作者：Kutrib Martin^*

来源：International Journal of General Systems, 2012, 41(6): 555-568.

DOI：10.1080/03081079.2012.695896

• cellular automata
• (limited) non-determinism
• language recognition
• computational capacity
• hierarchies
• parallel computing

We summarize results on non-deterministic cellular language acceptors. The non-determinism is regarded as limited resource. For parallel devices, it is natural to bound the non-determinism in time and/or space. Depending on the length of the input, the number of allowed non-deterministic state transitions as well as the number of non-deterministic cells at all is limited. We centre our attention to real-time, linear-time, and unrestricted-time computations and discuss the computational power of these machines. Speed-up results and the possibility to reduce the non-determinism as well as closure properties of languages acceptable with a constant number of non-deterministic transitions are presented. By considering the relations with context-free languages, several relations between the devices in question are implied. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved, and open problems for further research.

• 出版日期2012