Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Probabilistic Automata with Isolated Cut-Points
verfasst von : Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan
Erschienen in: Mathematical Foundations of Computer Science 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider various decision problems for probabilistic finite automata (PFA)s with isolated cut-points. Recall that a cut-point
x
is said to be isolated for a PFA if the acceptance probability of all finite strings is bounded away from
x
. First we establish the exact level of undecidability of the problem of determining if a cut-point is isolated; we show this problem to be
$\mathbf{\Sigma^0_2}$
-complete. Next we introduce a new class of PFAs called eventually weakly ergodic PFAs that generalize ergodic and weakly ergodic PFAs. We show that the emptiness and universality problem for these PFAs is decidable provided the cut-point is isolated.