KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

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
Publication language: russian,  pages: 36 (p. 103-138)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTex