Paper Info
Title
Non-Deterministic Cellular Automata And Languages
Abstract
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.
Year
DOI
Venue
2012
10.1080/03081079.2012.695896
INTERNATIONAL JOURNAL OF GENERAL SYSTEMS
Keywords
Field
DocType
cellular automata, (limited) non-determinism, language recognition, computational capacity, hierarchies, parallel computing
Cellular automaton,Computer science,Theoretical computer science,Language recognition,Artificial intelligence,Hierarchy,Machine learning,Computation
Journal
Volume
Issue
ISSN
41
6
0308-1079
Citations 
PageRank 
References 
0
0.34
17
Authors
1
Name
Order
Citations
PageRank
Martin Kutrib177889.77