Non-deterministic cellular automata and languages
From MaRDI portal
Publication:2869781
DOI10.1080/03081079.2012.695896zbMath1277.68153MaRDI QIDQ2869781
Publication date: 6 January 2014
Published in: International Journal of General Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/03081079.2012.695896
cellular automata; parallel computing; hierarchies; computational capacity; language recognition; (limited) non-determinism
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q80: Cellular automata (computational aspects)
Related Items
Complexity of One-Way Cellular Automata, Self-verifying Cellular Automata, A logical approach to locality in pictures languages
Cites Work
- On real time one-way cellular array
- On real-time cellular automata and trellis automata
- Characterizations and computational complexity of systolic trellis automata
- Iterative tree automata
- Relating the power of cellular arrays to their closure properties
- On time computability of functions in one-way cellular automata
- Deterministic one-way simulation of two-way real-time cellular automata and its related problems
- Computations on nondeterministic cellular automata
- Signals in one-dimensional cellular automata
- Alternation on cellular automata
- Relationships between nondeterministic and deterministic tape complexities
- Real-time language recognition by one-dimensional cellular automata
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- On One-Way Cellular Arrays
- One-way bounded cellular automata
- Some results on time-varying and relativised cellular automata*
- Real-time computations with restricted nondeterminism
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Tessellation Automata
- Quasi-realtime languages
- Simple Computation-Universal Cellular Spaces
