The power of nondeterminism and randomness for oblivious branching programs

DOI10.1007/S00224-002-1050-XzbMath1039.68083OpenAlexW1968742011MaRDI QIDQ1405793

Juraj Hromkovič, Martin Sauerhoff

Publication date: 26 August 2003

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-002-1050-x

zbMATH Keywords

ordered binary decision diagrams

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (8)

Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ On multi-partition communication complexity ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Width hierarchy for \(k\)-OBDD of small width ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ

This page was built for publication: The power of nondeterminism and randomness for oblivious branching programs