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

arrays of finite-state machinescomplexity of languagesinterconnected networksk-dimensional mesh-connected arraysspace-bounded TMtime-bounded ATMtree arraystriangular arrays

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Iterative arrays with direct central control
• Iterative tree arrays with logarithmic depth^†
• Iterative tree automata
• On iterative and cellular tree arrays
• On Some Open Problems in the Theory of Cellular Automata
• 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
• scientific article; zbMATH DE number 4060724 (Why is no real title available?)
• A batch-type time-true ATM-network simulator?design for parallel processing
• On some open problems concerning the complexity of cellular arrays
• 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)