Effective diagnostics of failures in automata networks. (Russian) Zbl 1016.94523

Summary: We study a representation of a finite automaton by a scheme in a basis of strongly connected finite automata. Previously we proposed a method for transforming an arbitrary part of a scheme into a subscheme which can be diagnosed by conditional tests leading to reasonable localization of inaccuracies from a broad class, see [Diskretn. Anal. Issled. Oper., Ser. 1 6, No. 1, 44-64 (1999; Zbl 0938.94024) and Diskretn. Anal. Issled. Oper., Ser. 1 7, No. 3, 45-71 (2000; Zbl 0957.94057)]. In the present paper, we propose a refinement of this method. We show that, under the additional restriction on the basis that there is a loop in the control flow graph of each automaton, the transformed schemes can be made more convenient for diagnostics and the test procedures for them, essentially shorter. An algorithm for obtaining tests is given, and estimates are presented for the length of tests and for the complexity of the transformed schemes.


94C12 Fault detection; testing in circuits and networks
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)