Comparing the Notions of Opacity for 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%2F21%3A73608388" target="_blank" >RIV/61989592:15310/21:73608388 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007%2Fs10626-021-00344-2" target="_blank" >https://link.springer.com/article/10.1007%2Fs10626-021-00344-2</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10626-021-00344-2" target="_blank" >10.1007/s10626-021-00344-2</a>
Alternative languages
Result language
angličtina
Original language name
Comparing the Notions of Opacity for Discrete-Event Systems
Original language description
Opacity is an information flow property characterizing whether a system reveals its secret to a passive observer. Several notions of opacity have been introduced in the literature. We study the notions of language-based opacity, current-state opacity, initial-state opacity, initial-and-final-state opacity, K-step opacity, and infinite-step opacity. Comparing the notions is a natural question that has been investigated and summarized by Wu and Lafortune, who provided transformations among current-state opacity, initial-and-final-state opacity, and language-based opacity, and, for prefix-closed languages, also between language-based opacity and initial-state opacity. We extend these results by showing that all the discussed notions of opacity are transformable to each other. Besides a deeper insight into the differences among the notions, the transformations have applications in complexity results. In particular, the transformations are computable in polynomial time and preserve the number of observable events and determinism, and hence the computational complexities of the verification of the notions coincide. We provide a complete and improved complexity picture of the verification of the discussed notions of opacity, and improve the algorithmic complexity of deciding language-based opacity, infinite-step opacity, and K-step opacity.
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
<a href="/en/project/LTAUSA19098" target="_blank" >LTAUSA19098: Verification and Control of Networked Discrete-Event Systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
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
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS
ISSN
0924-6703
e-ISSN
—
Volume of the periodical
31
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
30
Pages from-to
553-582
UT code for WoS article
000677919600001
EID of the result in the Scopus database
2-s2.0-85111379645