文章基本信息

标题：On Verification of Strong Periodic D-Detectability for Discrete Event Systems ⁎
本地全文：下载
作者：JiŘí Balun ; Tomáš Masopust
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2020
卷号：53
期号：4
页码：263-268
DOI：10.1016/j.ifacol.2021.04.025
语种：English
出版社：Elsevier
摘要：AbstractDetectability of discrete event systems has been introduced as a generalization of other state-estimation properties studied in the literature, including stability or observability. It is a property whether the current and subsequent states of a system can be determined based on observations. Since the requirement to exactly determine the current and subsequent states may be too strict in some applications, a relaxed notion of D-detectability has been introduced, distinguishing only certain pairs of states rather than all states. Four variants of D-detectability have been defined: strong (periodic) D-detectability and weak (periodic) D-detectability. The complexity of verifying weak (periodic) D-detectability follows from the results for verifying detectability, and hence is PSPACE-complete. Similarly, Shu and Lin constructed a detector that can check, in polynomial time, both strong (periodic) detectability and strong D-detectability. However, the case of strong periodic D-detectability is more involved, and, to the best of our knowledge, the question whether it can be verified in polynomial time is open. We answer this question by showing that there is no algorithm verifying the strong periodic D-detectability property in polynomial time, unless every problem solvable in polynomial space can be solved in polynomial time. Consequently, the algorithm based on the construction of the observer is the best possible. We further show that strong periodic D-detectability cannot be verified in polynomial time even for systems having only a single observable event, unless P = NP.
关键词：KeywordsDiscrete event systemsfinite-state automatadetectabilityverificationcomplexity