Complexity of One-Way Cellular Automata

DOI10.1007/978-3-319-18812-6_1zbMath1432.68281OpenAlexW1196156358MaRDI QIDQ5501608

Martin Kutrib

Publication date: 4 August 2015

Published in: Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18812-6_1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Related Items (3)

Iterative arrays with self-verifying communication cell ⋮ Iterative arrays with self-verifying communication cell ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• 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
• Signals in one-dimensional cellular automata
• Language not recognizable in real time by one-way cellular automata
• Fast one-way cellular automata.
• Relationships between nondeterministic and deterministic tape complexities
• Real-time language recognition by one-dimensional cellular automata
• Non-deterministic cellular automata and languages
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• On One-Way Cellular Arrays
• One-way bounded cellular automata
• Real-time computations with restricted nondeterminism
• Quasi-realtime languages
• Constructible functions in cellular automata and their applications to hierarchy results

This page was built for publication: Complexity of One-Way Cellular Automata