@inproceedings{f69dc365f9e94bc2a4f3ade38d65a404,
title = "Probabilistic automata with isolated cut-points",
abstract = "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 Σ20-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.",
author = "Rohit Chadha and Sistla, {A. Prasad} and Mahesh Viswanathan",
year = "2013",
month = oct,
day = "15",
doi = "10.1007/978-3-642-40313-2_24",
language = "English (US)",
isbn = "9783642403125",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "254--265",
booktitle = "Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings",
note = "38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 ; Conference date: 26-08-2013 Through 30-08-2013",
}