Show simple item record

dc.contributor.authorKeroglou, Christoforosen
dc.contributor.authorHadjicostis, Christoforos N.en
dc.creatorKeroglou, Christoforosen
dc.creatorHadjicostis, Christoforos N.en
dc.description.abstractIn 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 nondeterministic 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.en
dc.source2019 IEEE 58th Conference on Decision and Control (CDC)en
dc.titleVerification of AA-Diagnosability in Probabilistic Finite Automata is PSPACE-Harden
dc.description.endingpage6717Πολυτεχνική Σχολή / Faculty of EngineeringΤμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering
dc.type.uhtypeConference Objecten
dc.contributor.orcidHadjicostis, Christoforos N. [0000-0002-1706-708X]
dc.contributor.orcidKeroglou, Christoforos [0000-0002-6461-439X]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record