Decidability of Probabilistic Current-State Opacity for Probabilistic Finite Automata
Keru Chen, Shaowen Miao, Aiwen Lai, Ji Ma, Sihan Chen · 2024
Opacity holds significance as a critical property for probabilistic finite automata. Specifically, we center our attention on probabilistic current-state opacity, a property acknowledged to be generally undecidable. In this paper, we present a reduction from the problem of verifying probabilistic current-state opacity to the emptiness problem for finitely ambiguous stochastic automata. Subsequently, we establish that verifying probabilistic current-state opacity becomes feasible for probabilistic finite automata with finite ambiguity, and we conduct a complexity analysis of this problem.