|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2012, Number 2, Pages 13–22
(Mi ivm8429)
|
|
|
|
This article is cited in 14 scientific papers (total 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.
Received: 02.02.2011
Citation:
M. A. Alekhina, S. M. Grabovskaya, “Reliability of nonbranching programs in an arbitrary complete finite basis”, Izv. Vyssh. Uchebn. Zaved. Mat., 2012, no. 2, 13–22; Russian Math. (Iz. VUZ), 56:2 (2012), 10–18
Linking options:
https://www.mathnet.ru/eng/ivm8429 https://www.mathnet.ru/eng/ivm/y2012/i2/p13
|
|