Algoritmo baseado na busca de componentes fortemente conexos para verificação de diagnosticabilidade com intervalo de tempo ⋆

Abstract

Recently, the problem of fault diagnosability of discrete-event systems has been extended to the class of time-interval discrete-event systems, a class of discrete-event systems in which a unique clock controls the time elapsed between event occurrences. The model formalism used to deal with systems whose behavior is expressed in terms of regular languages is the so- called time-interval automaton. In a previous work, we proposed a diagnosability verification method inspired by the diagnoser proposed by Sampath et al. (1995), therefore relying on the search for indeterminate cycles in the diagnoser and corresponding cycles of Y-certain and N- certain states, in the labeled automaton; therefore, such a diagnoser does not carry enough information to ascertain if an observed cycle of uncertain states is an indeterminate cycle. In addition, the computational complexity of finding cycles is worse than exponential in the number of states, which makes this previous approach rather limited. In this paper, we propose a new diagnoser-based test automaton to verify the diagnosability of time-interval discrete- event systems inspired by that proposed in Viana e Basilio (2019) which relies on the search for strongly connected components (SCC) and, thus, with computational cost linear in the number of the test automaton transitions in the worst case.