A characterization of the power of vector machines

DOI10.1016/S0022-0000(76)80037-2zbMath0342.68033OpenAlexW2088300760MaRDI QIDQ1232182

Vaughan R. Pratt, Larry J. Stockmeyer

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(76)80037-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Turing machines and related notions (03D10)

Related Items (23)

Turing Machines for Dummies ⋮ Array processing machines: an abstract model ⋮ On nondeterminism in parallel computation ⋮ The problem of space invariance for sequential machines ⋮ On characterizations of the class PSPACE/poly ⋮ Parallel computation with threshold functions ⋮ The intrinsic difficulty of recursive functions ⋮ A canonical form of vector machines ⋮ Deterministic simulation of tape-bounded probabilistic Turing machine transducers ⋮ Tree-size bounded alternation ⋮ On uniform circuit complexity ⋮ Classifying the computational complexity of problems ⋮ On tape-bounded probabilistic Turing machine acceptors ⋮ Division in idealized unit cost RAMs ⋮ Lower bounds on the computational power of an optical model of computation ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ Circular Interval-valued Computers and Simulation of (Red-green) Turing Machines ⋮ Associative processors as a tool for maximal parallelism ⋮ Reflective relational machines ⋮ Optical computing ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ Speedups of deterministic machines by synchronous parallel machines ⋮ Parallel random access machines with powerful instruction sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An observation on time-storage trade off
• Time bounded random access machines
• Relationships between nondeterministic and deterministic tape complexities
• Classes of languages and linear-bounded automata
• Computational complexity of random access stored program machines
• Computability of Recursive Functions

This page was built for publication: A characterization of the power of vector machines