Article collection "Mathematical Problems of Cybernetics" №10, Moscow, 2001

Authors:Shevchenko V.I.

On complexity of diagnostics of non-elementary
closures in logic networks

Abstract:

We study time complexity of diagnostic algorithms of
logic networks depending on a number of inputs in a
network. Possible faults in networks are various
combinations of ∧- and ∨-closures
between themselves
and in combination with either constant faults or
faults of the 'negation' type. We use decision trees
(conditional tests) to diagnose such faults. We show
that, for diagnostics of an arbitrarily given
network with n, n ≥ 4, inputs, one needs to
submit
at least C(n)
input sets, and at most – 2n, depending on the type
of the logic gates in the network and the type of
faults, where C(n) is the sum of the numbers of
combinations from n - 1 to [(n - 1) / 2] and from n
- 1 to [(n - 1) / 2] + 1.

Keywords:

logic network, fault, complexity of diagnostics,
conditional test