The power of nondeterminism and randomness for oblivious branching programs
From MaRDI portal
Publication:1405793
DOI10.1007/s00224-002-1050-xzbMath1039.68083MaRDI 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
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Related Items
DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, Width hierarchy for \(k\)-OBDD of small width, Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance, On multi-partition communication complexity, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs, Reordering method and hierarchies for quantum and classical ordered binary decision diagrams