Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
DOI10.1016/0304-3975(89)90116-3zbMATH Open0678.68032OpenAlexW2014403984MaRDI QIDQ1124332FDOQ1124332
Authors: Jik H. Chang, Oscar H. Ibarra, Michael A. Palis 
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90116-3
Recommendations
- scientific article; zbMATH DE number 4060724
- scientific article; zbMATH DE number 3949715
- scientific article; zbMATH DE number 996551
- scientific article; zbMATH DE number 3868619
- Efficient Simulations among Several Models of Parallel Computers
- ON SIMULATING A CLASS OF PARALLEL ARCHITECTURES
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- scientific article; zbMATH DE number 1424440
- On space and time efficient TM simulations of some restricted classes of PDA's
triangular arraysinterconnected networkscomplexity of languagesarrays of finite-state machinesk-dimensional mesh-connected arraysspace-bounded TMtime-bounded ATMtree arrays
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- On uniform circuit complexity
- Alternation
- Simulation of Parallel Random Access Machines by Circuits
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
- Tree-size bounded alternation
- A universal interconnection pattern for parallel computers
- Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
- Speed of Recognition of Context-Free Languages by Array Automata
- Triangle cellular automata
- Iterative tree automata
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- Iterative tree arrays with logarithmic depth†
- Iterative arrays with direct central control
- A Generalized Dictionary Machine for VLSI
- On Some Open Problems in the Theory of Cellular Automata
- On iterative and cellular tree arrays
Cited In (5)
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- On some open problems concerning the complexity of cellular arrays
- Title not available (Why is that?)
- A batch-type time-true ATM-network simulator?design for parallel processing
- Low complexity classes of multidimensional cellular automata
This page was built for publication: Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124332)
