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

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

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 diagrams; finite automata; complexity measures; nondeterministic computation; Las Vegas computation; deterministic computation; computational power of randomized computations; one-way communication complexity

Mathematics Subject Classification ID

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

Related Items

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

Cites Work