On verification of strong periodic D-detectability for discrete event systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00537723" target="_blank" >RIV/67985840:_____/20:00537723 - isvavai.cz</a>
Alternative codes found
RIV/61989592:15310/21:73602410
Result on the web
<a href="http://dx.doi.org/10.1016/j.ifacol.2021.04.025" target="_blank" >http://dx.doi.org/10.1016/j.ifacol.2021.04.025</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ifacol.2021.04.025" target="_blank" >10.1016/j.ifacol.2021.04.025</a>
Alternative languages
Result language
angličtina
Original language name
On verification of strong periodic D-detectability for discrete event systems
Original language description
Detectability of discrete event systems was introduced as a generalization of other state-estimation properties. It asks whether the current and subsequent states of a system can be determined based on observations. To exactly determine the current and subsequent states may be too strict, therefore a relaxed notion of D-detectability was introduced. Four variants of D-detectability were defined: strong (periodic) D-detectability and weak (periodic) D-detectability. While deciding weak (periodic) D-detectability follows from deciding detectability (is PSpace-complete) and there is a polynomial-time algorithm deciding strong D-detectability, the case of strong periodic D-detectability is open. We answer this question by showing that there is no polynomial-time algorithm, unless P=PSPACE. There is no such algorithm even for systems having only a single observable event, unless P = NP.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
20205 - Automation and control systems
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
IFAC-PapersOnLine. Volume 53, Issue 4 - Proceedings of 15th IFAC Workshop on Discrete Event Systems WODES 2020
ISBN
—
ISSN
2405-8963
e-ISSN
—
Number of pages
6
Pages from-to
263-268
Publisher name
Elsevier
Place of publication
Amsterdam
Event location
Rio de Janeiro
Event date
Nov 11, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000651644000040