Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
type: Item
instance of: scholarly article
title: Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
zbMATH Open document ID: 0678.68032
DOI: 10.1016/0304-3975(89)90116-3
author: Jik H. Chang
author: Oscar H. Ibarra
author: Michael A. Palis
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4112005
zbMATH Keywords: complexity of languages
zbMATH Keywords: arrays of finite-state machines
zbMATH Keywords: tree arrays
zbMATH Keywords: triangular arrays
zbMATH Keywords: k-dimensional mesh-connected arrays
zbMATH Keywords: time-bounded ATM
zbMATH Keywords: space-bounded TM
zbMATH Keywords: interconnected networks
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90116-3
OpenAlex ID: W2014403984
cites work: A Generalized Dictionary Machine for VLSI
cites work: Alternation
cites work: Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
cites work: Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
cites work: Iterative tree automata
cites work: Iterative tree arrays with logarithmic depth†
cites work: Triangle cellular automata
cites work: A universal interconnection pattern for parallel computers
cites work: Q3862379
cites work: Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
cites work: On iterative and cellular tree arrays
cites work: On Some Open Problems in the Theory of Cellular Automata
cites work: Speed of Recognition of Context-Free Languages by Array Automata
cites work: Tree-size bounded alternation
cites work: On uniform circuit complexity
cites work: Iterative arrays with direct central control
cites work: Simulation of Parallel Random Access Machines by Circuits
Recommended article: Q3795230
Recommended article: Q3719832
Recommended article: Q3127072
Recommended article: Q3334991
Recommended article: Efficient Simulations among Several Models of Parallel Computers
Recommended article: ON SIMULATING A CLASS OF PARALLEL ARCHITECTURES
Recommended article: Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
Recommended article: Q4945675
Recommended article: On space and time efficient TM simulations of some restricted classes of PDA's
description: scientific article; zbMATH DE number 4112005