Abstract
We study theoretical problems of fault diagnosis in circuits and switching networks, which are among the most fundamental models for computing Boolean functions. We investigate two main cases: when the scheme (circuit or switching network) has the same mode of operation for both calculation and diagnostics, and when the scheme has two modes of operation -- normal for calculation and special for diagnostics. In the former case, we get mostly negative results, including superpolynomial lower bounds on the minimum depth of diagnostic decision trees depending on scheme complexity and the NP-hardness of construction diagnostic decision trees. In the latter case, we describe classes of schemes and types of faults for which decision trees can be effectively used to diagnose schemes, when they are transformed into so-called iteration-free schemes.
Brief Biography
Mikhail Moshkov is a professor in the CEMSE Division at King Abdullah University of Science and Technology, Saudi Arabia since October 1, 2008. He earned a master's degree from Nizhni Novgorod State University, received his doctorate from Saratov State University, and habilitation from Moscow State University. From 1977 to 2004, Dr. Moshkov was with Nizhni Novgorod State University. Since 2003 he worked in Poland at the Institute of Computer Science, University of Silesia, and since 2006 also in the Katowice Institute of Information Technologies. His main areas of research are the complexity of algorithms, combinatorial optimization, and data mining. Dr. Moshkov is the author or co-author of nine research monographs published by Springer.
