Infinite vs. finite size-bounded randomized computations

DOI10.1016/J.JCSS.2013.11.004MaRDI QIDQ2637645zbMATH OpenOpenAlexFDO

Authors Richard Královič

Publication date 13 February 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2013.11.004

zbMATH Keywords

Las Vegas randomizationprobabilistic computationsrotating finite automatasize complexitysweeping finite automatatime complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• scientific article; zbMATH DE number 1405658
• A lower bound for probabilistic algorithms for finite state machines
• On the power of Las Vegas II: Two-way finite automata
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations

Cites work

• A note on two-way probabilistic automata
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Amplification of slight probabilistic advantage at absolutely no cost in space
• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Computational Complexity of Probabilistic Turing Machines
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• On the power of Las Vegas II: Two-way finite automata
• Probabilistic automata
• Size complexity of rotating and sweeping automata
• Small Sweeping 2NFAs Are Not Closed Under Complement
• The method of forced enumeration for nondeterministic automata

Cited in

(2)

• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• The strength of non-size increasing computation

This page was built for publication: Infinite vs. finite size-bounded randomized computations

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