Amplification of slight probabilistic advantage at absolutely no cost in space
From MaRDI portal
Publication:1607005
DOI10.1016/S0020-0190(99)00129-5zbMath0999.68067OpenAlexW2087974580MaRDI QIDQ1607005
Ioan I. Macarie, Joel I. Seiferas
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00129-5
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Infinite vs. finite size-bounded randomized computations ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ Size complexity of rotating and sweeping automata ⋮ On the power of randomized multicounter machines ⋮ Size Complexity of Two-Way Finite Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Multihead two-way probabilistic finite automata
- Space-bounded hierarchies and probabilistic computations
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Relating refined space complexity classes
- Characterization of realizable space complexities
- On non-determinacy in simple computing devices
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- Computational Complexity of Probabilistic Turing Machines
- Some Results on Tape-Bounded Turing Machines
This page was built for publication: Amplification of slight probabilistic advantage at absolutely no cost in space
