A Note on Las Vegas OBDDs.

Rustam Mubarakzjanov: A Note on Las Vegas OBDDs CSIT 1999 : E/E

Abstract

We prove that the error free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for Las Vegas read once branching programs.

Copyright © 1999 by the Institute for Contemporary Education "JurInfoR-MSU". Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the CSIT copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute for Contemporary Education JMSUICE. To copy otherwise, or to republish, requires a fee and/or special permission from the JMSUICE.

Printed Edition

Ch. Freytag and V. Wolfengagen (Eds.): CSIT'99, Proceedings of 1st International Workshop on Computer Science and Information Technologies, January 18-22, 1999, Moscow, Russia. MEPhI Publishing 1999, ISBN 5-7262-0263-5

Electronic Edition