On tape-bounded probabilistic Turing machine acceptors

DOI10.1016/0304-3975(81)90032-3MaRDI QIDQ1158756zbMATH OpenOpenAlexFDO

Authors Janos Simon

Publication date 1981

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(81)90032-3

zbMATH Keywords

deterministic and probabilistic tape complexities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A characterization of the power of vector machines
• Computational Complexity of Probabilistic Turing Machines
• Fast Parallel Matrix Inversion Algorithms
• scientific article; zbMATH DE number 3532523 (Why is no real title available?)
• scientific article; zbMATH DE number 3568040 (Why is no real title available?)
• scientific article; zbMATH DE number 3592964 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Probabilistic Turing Machines and Computability
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(9)

• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• Division in idealized unit cost RAMs
• A survey of space complexity
• The time-precision tradeoff problem on on-line probabilistic Turing machines
• Relationships among $PL$, $\#L$, and the determinant
• On counting propositional logic and Wagner's hierarchy
• Approximating iterated multiplication of stochastic matrices in small space
• Decreasing the bandwidth of a transition matrix
• Probabilistic Turing machines and recursively enumerable Dedekind cuts

This page was built for publication: On tape-bounded probabilistic Turing machine acceptors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158756)