On the power of randomized multicounter machines

DOI10.1016/J.TCS.2004.09.015MaRDI QIDQ1763706zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

DeterminismMulticounter machinesNondeterminismProblem complexityRandomness

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 2038700
• Alternating multicounter machines with constant number of reversals
• scientific article; zbMATH DE number 3982518
• A note on real-time one-way alternating multicounter machines
• scientific article; zbMATH DE number 1405658

Cites work

• Amplification of slight probabilistic advantage at absolutely no cost in space
• Communication complexity
• Communication Complexity
• Computational Complexity of Probabilistic Turing Machines
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• scientific article; zbMATH DE number 1500514 (Why is no real title available?)
• scientific article; zbMATH DE number 2087229 (Why is no real title available?)
• scientific article; zbMATH DE number 1857650 (Why is no real title available?)
• scientific article; zbMATH DE number 1405658 (Why is no real title available?)
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• On the distributional complexity of disjointness
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Projections of languages recognizable by probabilistic and alternating finite multitape automata
• Properties of probabilistic pushdown automata
• The Probabilistic Communication Complexity of Set Intersection

Cited in

(11)

• On read-once vs. multiple access to randomness in logspace
• Nondeterministic multicounter machines and complementation
• On the complexity of decision problems for counter machines with applications to coding theory
• scientific article; zbMATH DE number 1670881 (Why is no real title available?)
• Simulations by time-bounded counter machines
• On the Power of the Randomized Iterate
• scientific article; zbMATH DE number 3872684 (Why is no real title available?)
• scientific article; zbMATH DE number 4215365 (Why is no real title available?)
• Simulations by Time-Bounded Counter Machines
• scientific article; zbMATH DE number 697824 (Why is no real title available?)
• scientific article; zbMATH DE number 2038700 (Why is no real title available?)

This page was built for publication: On the power of randomized multicounter machines

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