Back to Search
Start Over
Verification of AA-Diagnosability in Probabilistic Finite Automata is PSPACE-Hard
- Publication Year :
- 2019
-
Abstract
- In this paper we consider the complexity of verifying the property of AA-diagnosability in probabilistic finite automata and establish that AA-diagnosability is, in general, a PSPACE-hard problem. In deterministic and non-deterministic finite automata, the property of diagnosability captures our ability to determine, based on our observation of the activity in a given finite automaton, the occurrence of any fault event, at least if we wait for at most a finite number of events (following the occurrence of the unobservable fault event). In stochastic settings where the underlying system is a probabilistic finite automaton under partial observation, there is not a prevalent notion of diagnosability and many variations have been proposed, including A-diagnosability and AA-diagnosability. Earlier work has shown that the verification of A-diagnosability (also referred to as strong stochastic diagnosability) for a given probabilistic finite automaton is a PSPACE-hard problem. In this paper, we establish that the verification of AA-diagnosability (also referred to as stochastic diagnosability) is a PSPACE-hard problem.<br />QC 20201007
Details
- Database :
- OAIster
- Notes :
- Keroglou, Christoforos, Hadjicostis, Christoforos N.
- Publication Type :
- Electronic Resource
- Accession number :
- edsoai.on1235096533
- Document Type :
- Electronic Resource
- Full Text :
- https://doi.org/10.1109.CDC40024.2019.9029364