On some open problems concerning the complexity of cellular arrays
From MaRDI portal
Publication:6183605
DOI10.1007/3-540-58131-6_47zbMath1529.68174OpenAlexW1562219526MaRDI QIDQ6183605
Publication date: 29 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58131-6_47
Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On real-time cellular automata and trellis automata
- Characterizations and computational complexity of systolic trellis automata
- Two-dimensional iterative arrays: Characterizations and applications
- Relating the power of cellular arrays to their closure properties
- Optimal simulation of tree arrays by linear arrays
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- On iterative and cellular tree arrays
- Deterministic one-way simulation of two-way real-time cellular automata and its related problems
- Relationships between nondeterministic and deterministic tape complexities
- Tape bounds for time-bounded Turing machines
- Real-time language recognition by one-dimensional cellular automata
- Systolic trellis automatata †
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- On One-Way Cellular Arrays
- Iterative tree arrays with logarithmic depth†
- Triangle cellular automata
- Alternation
- On Some Open Problems in the Theory of Cellular Automata
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Cellular automata complexity trade-offs
This page was built for publication: On some open problems concerning the complexity of cellular arrays