On some open problems concerning the complexity of cellular arrays

DOI10.1007/3-540-58131-6_47MaRDI QIDQ6183605zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Tao Jiang

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Recommendations

• On the computational complexity of finite cellular automata
• scientific article; zbMATH DE number 17562
• Cellular automata -- a computational point of view
• scientific article; zbMATH DE number 4026835
• Complexity issues in computational biology

Cites work

• scientific article; zbMATH DE number 3872685 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Alternation
• Cellular automata complexity trade-offs
• Characterizations and computational complexity of systolic trellis automata
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
• Iterative tree arrays with logarithmic depth^†
• On One-Way Cellular Arrays
• On Some Open Problems in the Theory of Cellular Automata
• On iterative and cellular tree arrays
• On real-time cellular automata and trellis automata
• Optimal simulation of tree arrays by linear arrays
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-time language recognition by one-dimensional cellular automata
• Relating the power of cellular arrays to their closure properties
• Relationships between nondeterministic and deterministic tape complexities
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Systolic trellis automatata †
• Tape bounds for time-bounded Turing machines
• Triangle cellular automata
• Two-dimensional iterative arrays: Characterizations and applications

This page was built for publication: On some open problems concerning the complexity of cellular arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183605)