Number of the records: 1
Opacity of Discrete Event Systems: Transformations and Algorithms
Title statement Opacity of Discrete Event Systems: Transformations and Algorithms [rukopis] / Jiří Balun Additional Variant Titles Výpočetní a stavová složitost vlastností diskrétních systémů Personal name Balun, Jiří (dissertant) Translated title Computational and state complexity of properties of discrete event systems Issue data 2023 Phys.des. 125 Note Ved. práce Radim Bělohlávek Another responsib. Bělohlávek, Radim, 1971- (předseda oborové rady) Another responsib. Univerzita Palackého. Katedra informatiky (degree grantor) Keywords Discrete event system * finite automaton * opacity * transformation * complexity * algorithm * verification * Discrete event system * finite automaton * opacity * transformation * complexity * algorithm * verification Form, Genre disertace dissertations UDC (043.3) Country Česko Language angličtina Document kind PUBLIKAČNÍ ČINNOST Title Ph.D. Degree program Doktorský Degree program Informatika Degreee discipline Informatika 
book
Kvalifikační práce Downloaded Size datum zpřístupnění 00263936-281104300.pdf 9 1.4 MB 29.06.2023 Posudek Typ posudku 00263936-opon-764726089.pdf Posudek oponenta 00263936-ved-474465858.pdf Posudek vedoucího 00263936-opon-454976152.pdf Posudek oponenta Průběh obhajoby datum zadání datum odevzdání datum obhajoby přidělená hodnocení typ hodnocení 00263936-prubeh-864541201.pdf 26.09.2013 29.06.2023 12.10.2023 S Hodnocení známkou
Opacity is a security property of discrete-event systems that asks whether, at any point of a computation, the secret is revealed to a passive intruder. The literature has introduced several notions of opacity, including language-based opacity, trace opacity, current-state opacity, weak k-step opacity, weak infinite-step opacity, strong k-step opacity, initial-state opacity, and initial-and-final-state opacity. In this work, we provide a complete and improved complexity picture of verifying the discussed opacity notions within the finite automata model. First, we focus on the complexity of deciding current-state opacity in systems with a restricted set of events and a restricted structure. Second, we present polynomial-time transformations among the notions that preserve determinism and the number of observable events, allowing the generalization of results across different notions of opacity. Third, we propose three new algorithms for verifying language-based opacity, trace opacity, weak k-step opacity, weak infinite-step opacity, and strong k-step opacity that improve their respective algorithmic complexity.Opacity is a security property of discrete-event systems that asks whether, at any point of a computation, the secret is revealed to a passive intruder. The literature has introduced several notions of opacity, including language-based opacity, trace opacity, current-state opacity, weak k-step opacity, weak infinite-step opacity, strong k-step opacity, initial-state opacity, and initial-and-final-state opacity. In this work, we provide a complete and improved complexity picture of verifying the discussed opacity notions within the finite automata model. First, we focus on the complexity of deciding current-state opacity in systems with a restricted set of events and a restricted structure. Second, we present polynomial-time transformations among the notions that preserve determinism and the number of observable events, allowing the generalization of results across different notions of opacity. Third, we propose three new algorithms for verifying language-based opacity, trace opacity, weak k-step opacity, weak infinite-step opacity, and strong k-step opacity that improve their respective algorithmic complexity.
Number of the records: 1