On verification of strong periodic D-detectability for discrete event systems

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/61989592:15310/21:73602410

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On verification of strong periodic D-detectability for discrete event systems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On verification of strong periodic D-detectability for discrete event systems

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20205 - Automation and control systems

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

IFAC-PapersOnLine. Volume 53, Issue 4 - Proceedings of 15th IFAC Workshop on Discrete Event Systems WODES 2020

ISBN

—

ISSN

2405-8963

e-ISSN

—

Počet stran výsledku

6

Strana od-do

263-268

Název nakladatele

Elsevier

Místo vydání

Amsterdam

Místo konání akce

Rio de Janeiro

Datum konání akce

11. 11. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000651644000040