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

From MaRDI portal
Publication:1854456

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




Related Items (26)

Infinite vs. finite size-bounded randomized computationsComplementing two-way finite automataFrom Quantum Query Complexity to State ComplexitySelf-verifying Cellular AutomataExact Affine Counter AutomataSize complexity of rotating and sweeping automataLifting query complexity to time-space complexity for two-way finite automataProbabilism versus Alternation for AutomataClassical and Quantum Computations with Restricted MemoryError-Free Affine, Unitary, and Probabilistic OBDDsPairs of complementary unary languages with ``balanced nondeterministic automataGeneralizations of the distributed Deutsch–Jozsa promise problemOn the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their SizesSelf-Verifying Pushdown and Queue AutomataOn the power of randomized multicounter machinesAn upper bound for transforming self-verifying automata into deterministic onesOptimal simulation of self-verifying automata by deterministic automataOn the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA'sQuantum branching programs and space-bounded nonuniform quantum complexityOn probabilistic pushdown automataIterative arrays with self-verifying communication cellConverting Self-verifying Automata into Deterministic AutomataSize Complexity of Two-Way Finite AutomataSelf-Verifying Finite Automata and Descriptional ComplexityNote on the complexity of Las Vegas automata problemsCommunication complexity method for measuring nondeterminism in finite automata



Cites Work


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