Reliability of nonbranching programs in an arbitrary complete finite basis

被引：0

作者：

M. A. Alekhina

S. M. Grabovskaya

机构：

[1] Penza State University,

来源：

Russian Mathematics | 2012年 / 56卷 / 2期

关键词：

Boolean functions; nonbranching programs; conditional stop operator; synthesis; reliability;

D O I：

10.3103/S1066369X12020028

中图分类号：

学科分类号：

摘要：

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 ɛ ∈ (0, 1/960].

引用

页码：10 / 18

页数：8

共 5 条

[1] Chashkin A. V.(1997)On the Average Time for the Computation of the Values of Boolean Functions Diskretn. Analiz i Issled. Operatsii 4 60-78
[2] Alekhina M. A.(2009)On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables Uchen. Zap. Kazansk. Un-ta. Ser. Fiz.-Matem. Nauki 151 25-35
[3] Vasin A. V.(2009)Synthesis of Asymptotically Optimal Reliable Circuits in Basis { Diskretn. Analiz i Issled. Operatsii 16 12-22
[4] Vasin A. V.(2012)& Diskretn. Analiz i Issled. Operatsii 19 49-56
[5] Grabovskaya S. M.(undefined), undefined undefined undefined-undefined

← 1 →