Geodesic
The capabilities of probabilistic ordered read-$k$-times binary programs and deterministic read-once binary programs are incomparable
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2005), pp. 34-43.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{IVM_2005_11_a5,
     author = {R. G. Mubarakzyanov},
     title = {The capabilities of probabilistic ordered read-$k$-times binary programs and deterministic read-once binary programs are incomparable},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {34--43},
     publisher = {mathdoc},
     number = {11},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2005_11_a5/}
}
TY  - JOUR
AU  - R. G. Mubarakzyanov
TI  - The capabilities of probabilistic ordered read-$k$-times binary programs and deterministic read-once binary programs are incomparable
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2005
SP  - 34
EP  - 43
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2005_11_a5/
LA  - ru
ID  - IVM_2005_11_a5
ER  - 
%0 Journal Article
%A R. G. Mubarakzyanov
%T The capabilities of probabilistic ordered read-$k$-times binary programs and deterministic read-once binary programs are incomparable
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2005
%P 34-43
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2005_11_a5/
%G ru
%F IVM_2005_11_a5
R. G. Mubarakzyanov. The capabilities of probabilistic ordered read-$k$-times binary programs and deterministic read-once binary programs are incomparable. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2005), pp. 34-43. http://geodesic.mathdoc.fr/item/IVM_2005_11_a5/

[1] Wegener I., Branching programs and binary desicion diagrams: theory and applications, SIAM monographs on discrete mathematics and applications, Philadelphia, USA, 2000, 408 pp. | MR

[2] Bryant R.E., “Graph-based algorithms for Boolean function manipulation”, IEEE Transact. on Comput., 35 (1986), 677–691 | DOI | Zbl

[3] Barington D.A., “Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^1$”, J. Comput. and System Sci., 38 (1989), 150–164 | DOI | MR

[4] Newman I., “Testing of function that have small width branching programs”, IEEE Computer Society, Proc. of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000 (Redondo Beach, California, USA, 12–14 November 2000), 251–258 | MR

[5] Agrawal M., Thierauf T., “The satisfiability problem for probabilistic ordered branching programs”, Theory Comput. Systems (TOCS), 34 (2001), 471–487 | MR | Zbl

[6] Ablayev F., “Randomization and nondeterminism are incomparable for ordered read-once branching programs”, Proc. ICALP'97, LNCS, 1256, Springer, 1997, 195–202 | MR

[7] Ablayev F., Karpinski M., Mubarakzjanov R., “On $BPP$ versus $NP \cup coNP$ for ordered read-once branching programs”, Theoret. Comput. Sci., 264 (2001), 127–137 | DOI | MR | Zbl

[8] Karpinski M., Mubarakzjanov R., “Some separation problems on randomized OBDDs”, Proc. of the Workshop on Computer Science and Information Technologies CSIT'99 (Moscow, Russia, 1999)

[9] Karpinski M., Mubarakzjanov R., “A note on Las Vegas OBDDs”, Electronical Colloquium on Computational Complexity, ECCC TR99-009 (Trier University, Trier, 1999)

[10] Sauerhoff M., “Randomness and nondeterminism are incomparable for read-once branching programs”, Electronical Colloquium on Computational Complexity, ECCC TR98-018 (Trier University, Trier, 1998)

[11] Gergov J., Meinel C., “Efficient Boolean manipulation with OBDDs can be extended to FBDDs”, IEEE Transact. on Comput., 43:10 (1994), 1197–1209 | DOI | Zbl

[12] Sieling D., Wegener I., “Graph driven BDDs — a new data structure for Boolean functions”, Theoret. Comput. Sci., 141 (1995), 283–310 | DOI | MR | Zbl

[13] Paturi R., Simon J., “Probabilistic communication complexity”, J. Comput. and System Sci., 33:1 (1986), 106–123 | DOI | MR | Zbl

[14] Mubarakzjanov R., “Bounded-width probabilistic OBDDs and read-once branching programs are incomparable”, Electronical Colloquium on Computational Complexity, ECCC TR01-037 (Trier University, Trier, 2001)

[15] Mubarakzjanov R., “On probabilistic OBDDs with constant width”, Proc. of the Workshop on Comput. Sci. and Informat. Technolog. CSIT'2000 (Ufa, Russia, September 18–23, 2000), 2, 62–68

[16] Mubarakzjanov R., “Probabilistic OBDDs: on bound of width versus bound of error”, Electronical Colloquium on Computational Complexity, ECCC TR00-085 (Trier University, Trier, 2000)

[17] Forster J., “A linear lower bound on the unbounded error probabilistic communication complexity”, J. Comput. and System Sci., 65:4 (2002), 612–625 | DOI | MR | Zbl