On the power of randomized multicounter machines
From MaRDI portal
Publication:1763706
DOI10.1016/j.tcs.2004.09.015zbMath1078.68037MaRDI QIDQ1763706
Juraj Hromkovič, Georg Schnitger
Publication date: 22 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.015
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Related Items
Cites Work
- Communication complexity
- Projections of languages recognizable by probabilistic and alternating finite multitape automata
- On the distributional complexity of disjointness
- Properties of probabilistic pushdown automata
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Amplification of slight probabilistic advantage at absolutely no cost in space
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- The Probabilistic Communication Complexity of Set Intersection
- Computational Complexity of Probabilistic Turing Machines
- Communication Complexity
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item