Verifying weak and strong k-step opacity in discrete-event systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F23%3A73620757" target="_blank" >RIV/61989592:15310/23:73620757 - isvavai.cz</a>
Result on the web
<a href="https://www.sciencedirect.com/science/article/pii/S0005109823003138" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0005109823003138</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.automatica.2023.111153" target="_blank" >10.1016/j.automatica.2023.111153</a>
Alternative languages
Result language
angličtina
Original language name
Verifying weak and strong k-step opacity in discrete-event systems
Original language description
Opacity is an important system-theoretic property expressing whether a system may reveal its secret to a passive observer (an intruder) who knows the structure of the system but has only limited observations of its behavior. Several notions of opacity have been discussed in the literature, including current-state opacity, k-step opacity, and infinite-step opacity. We investigate weak and strong kstep opacity, the notions that generalize both current-state opacity and infinite-step opacity, and ask whether the intruder is not able to decide, at any time instant, when respectively whether the system was in a secret state during the last k observable steps. We design a new algorithm verifying weak k-step opacity, the complexity of which is lower than the complexity of existing algorithms and does not depend on the parameter k, and show how to use it to verify strong k-step opacity by reducing strong k-step opacity to weak k-step opacity. The complexity of the resulting algorithm is again better than the complexity of existing algorithms and does not depend on the parameter k.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
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
Name of the periodical
AUTOMATICA
ISSN
0005-1098
e-ISSN
1873-2836
Volume of the periodical
155
Issue of the periodical within the volume
SEP
Country of publishing house
US - UNITED STATES
Number of pages
12
Pages from-to
"111153-1"-"111153-12"
UT code for WoS article
001026237100001
EID of the result in the Scopus database
2-s2.0-85162198427