The time-precision tradeoff problem on on-line probabilistic Turing machines

DOI10.1016/0304-3975(83)90133-0zbMath0509.68045OpenAlexW2087065633MaRDI QIDQ1838301

Osamu Watanabe

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90133-0

zbMATH Keywords

probabilistic Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

The complexity properties of probabilistic automata with isolated cut point ⋮ Comparative complexity of the representation of languages by probabilistic automata ⋮ Probabilistic Turing machines and recursively enumerable Dedekind cuts

Cites Work

• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• On tape-bounded probabilistic Turing machine acceptors
• On the computational power of pushdown automata
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Probabilistic Algorithms in Finite Fields
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Boolean Memories
• A note on computing time for recognition of languages generated by linear grammars
• Probabilistic automata
• Recognition time of context-free languages by on-line Turing machines
• Unnamed Item
• Unnamed Item
• Unnamed Item