Complexity of One-Way Cellular Automata
From MaRDI portal
Publication:5501608
DOI10.1007/978-3-319-18812-6_1zbMath1432.68281OpenAlexW1196156358MaRDI QIDQ5501608
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
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
