id: 06108778
dt: j
an: 06108778
au: Alekhina, M.A.; Grabovskaya, S.M.
ti: Reliability of nonbranching programs in an arbitrary complete finite basis.
so: Russ. Math. 56, No. 2, 10-18 (2012); translation from Izv. Vyssh. Uchebn.
    Zaved., Mat. 2012, No. 2, 13-22 (2012).
py: 2012
pu: Pleiades Publishing (Allerton Press, Inc.), New York; Springer, New York
la: EN
cc: 
ut: Boolean functions; nonbranching programs; conditional stop operator;
    synthesis; reliability
ci: 
li: doi:10.3103/S1066369X12020028
ab: Summary: We consider the realization of Boolean functions by nonbranching
    programs with conditional stop operators in an arbitrary complete
    finite basis. We assume that conditional stop operators are absolutely
    reliable, while all functional operators are prone to output inverse
    failures independently of each other with probability $ε$ in the
    interval $(0, 1/2)$. We prove that any Boolean function is realizable
    by a program with unreliability $ε+ 81ε^2$ for all $ε\in (0,
    1/960]$.
rv: