Non-deterministic cellular automata and languages

DOI10.1080/03081079.2012.695896zbMath1277.68153OpenAlexW2060130646MaRDI QIDQ2869781

Martin Kutrib

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

zbMATH Keywords

cellular automataparallel computinghierarchiescomputational capacitylanguage recognition(limited) non-determinism

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Related Items (4)

A logical approach to locality in pictures languages ⋮ Self-verifying Cellular Automata ⋮ Shrinking one-way cellular automata ⋮ Complexity of One-Way Cellular Automata

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

This page was built for publication: Non-deterministic cellular automata and languages