Among notions of detectability for a discrete-event system (DES), strong detectability implies that after a finite number of observations to every infinitely long output/label sequence generated by the DES, the current state can be uniquely determined. This notion is strong so that by using it the current state can be easily determined. In order to keep the advantage of strong detectability and weaken its disadvantage, we can additionally take some subsequent outputs into account in order to determine the current state. Such a modified observation will make some DES that is not strongly detectable become strongly detectable in a weaker sense, which we call K-delayed strong detectability if we observe at least K outputs after the time at which the state need to be determined. In this paper, we study K-delayed strong detectability for DESs modeled by finite-state automata (FSAs), and give a polynomial-time verification algorithm by using a novel concurrent-composition method. Note that the algorithm applies to all FSAs. Also by the method, an upper bound for K has been found, and we also obtain polynomial-time verification algorithms for (k1, k)-detectability and (k1, k)-D-detectability of FSAs firstly studied by [Shu and Lin, 2013]. Our algorithms strength the corresponding polynomial-time verification algorithms given by Shu and Lin based on the usual assumptions of deadlock-freeness and promptness (i.e., there is no reachable unobservable cycle).

K-delayed strong detectability of discrete-event systems

Zhang K.;Giua A.
2019-01-01

Abstract

Among notions of detectability for a discrete-event system (DES), strong detectability implies that after a finite number of observations to every infinitely long output/label sequence generated by the DES, the current state can be uniquely determined. This notion is strong so that by using it the current state can be easily determined. In order to keep the advantage of strong detectability and weaken its disadvantage, we can additionally take some subsequent outputs into account in order to determine the current state. Such a modified observation will make some DES that is not strongly detectable become strongly detectable in a weaker sense, which we call K-delayed strong detectability if we observe at least K outputs after the time at which the state need to be determined. In this paper, we study K-delayed strong detectability for DESs modeled by finite-state automata (FSAs), and give a polynomial-time verification algorithm by using a novel concurrent-composition method. Note that the algorithm applies to all FSAs. Also by the method, an upper bound for K has been found, and we also obtain polynomial-time verification algorithms for (k1, k)-detectability and (k1, k)-D-detectability of FSAs firstly studied by [Shu and Lin, 2013]. Our algorithms strength the corresponding polynomial-time verification algorithms given by Shu and Lin based on the usual assumptions of deadlock-freeness and promptness (i.e., there is no reachable unobservable cycle).
2019
978-1-7281-1398-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/299255
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact