On some open problems concerning the complexity of cellular arrays

DOI10.1007/3-540-58131-6_47zbMATH Open1529.68174OpenAlexW1562219526MaRDI QIDQ6183605FDOQ6183605

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Relationships between nondeterministic and deterministic tape complexities
• Alternation
• On One-Way Cellular Arrays
• Systolic trellis automatata †
• Characterizations and computational complexity of systolic trellis automata
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Two-dimensional iterative arrays: Characterizations and applications
• Real-time language recognition by one-dimensional cellular automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• On real-time cellular automata and trellis automata
• Cellular automata complexity trade-offs
• Relating the power of cellular arrays to their closure properties
• Title not available (Why is that?)
• Triangle cellular 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^†
• Tape bounds for time-bounded Turing machines
• On Some Open Problems in the Theory of Cellular Automata
• Optimal simulation of tree arrays by linear arrays
• On iterative and cellular tree arrays

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)