On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata

DOI10.1006/inco.2001.3040zbMath1007.68065OpenAlexW2072453354MaRDI QIDQ1854456

Georg Schnitger, Juraj Hromkovič

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3040

zbMATH Keywords

ordered binary decision diagramsfinite automatacomplexity measuresnondeterministic computationLas Vegas computationdeterministic computationcomputational power of randomized computationsone-way communication complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (26)

Infinite vs. finite size-bounded randomized computations ⋮ Complementing two-way finite automata ⋮ From Quantum Query Complexity to State Complexity ⋮ Self-verifying Cellular Automata ⋮ Exact Affine Counter Automata ⋮ Size complexity of rotating and sweeping automata ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Probabilism versus Alternation for Automata ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Self-Verifying Pushdown and Queue Automata ⋮ On the power of randomized multicounter machines ⋮ An upper bound for transforming self-verifying automata into deterministic ones ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ On probabilistic pushdown automata ⋮ Iterative arrays with self-verifying communication cell ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Size Complexity of Two-Way Finite Automata ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Note on the complexity of Las Vegas automata problems ⋮ Communication complexity method for measuring nondeterminism in finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Communication complexity
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Relationships between nondeterministic and deterministic tape complexities
• On quantum and probabilistic communication
• Graph-Based Algorithms for Boolean Function Manipulation
• Communication Complexity

This page was built for publication: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata