RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2012 Number 2, Pages 13–22 (Mi ivm8429)

This article is cited in 14 papers

Reliability of nonbranching programs in an arbitrary complete finite basis

M. A. Alekhina, S. M. Grabovskaya

Chair of Discrete Mathematics, Penza State University, Penza, Russia

Abstract: 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 $\varepsilon$ from the interval (0,1/2). We prove that any Boolean function is realizable by a nonbranching program with unreliability $\varepsilon+81\varepsilon^2$ for all $\varepsilon\in(0,1/960]$.

Keywords: Boolean functions, nonbranching programs, conditional stop-operator, synthesis, reliability.

UDC: 519.718

Received: 02.02.2011


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2012, 56:2, 10–18

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024