Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs

DOI10.1016/0304-3975(89)90116-3MaRDI QIDQ1124332zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

triangular arraysinterconnected networkscomplexity of languagesarrays of finite-state machinesk-dimensional mesh-connected arraysspace-bounded TMtime-bounded ATMtree arrays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A Generalized Dictionary Machine for VLSI
• A universal interconnection pattern for parallel computers
• Alternation
• Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
• Iterative arrays with direct central control
• Iterative tree arrays with logarithmic depth^†
• Iterative tree automata
• On Some Open Problems in the Theory of Cellular Automata
• On iterative and cellular tree arrays
• On uniform circuit complexity
• Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Simulation of Parallel Random Access Machines by Circuits
• Speed of Recognition of Context-Free Languages by Array Automata
• Tree-size bounded alternation
• Triangle cellular automata

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
• scientific article; zbMATH DE number 4060724 (Why is no real title available?)
• 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)