@inproceedings{a368d973ee164323a9d7be2f0526dfad,
title = "Approximating probabilistic automata by regular languages",
abstract = "A probabilistic finite automaton (PFA) A is said to be regular-approximable with respect to (x, y), if there is a regular language that contains all words accepted by A with probability at least x+y, but does not contain any word accepted with probability at most x. We show that the problem of determining if a PFA A is regular-approximable with respect to (x, y) is not recursively enumerable. We then show that many tractable sub-classes of PFAs identified in the literature-hierarchical PFAs, polynomially ambiguous PFAs, and eventually weakly ergodic PFAs-are regular-approximable with respect to all (x, y). Establishing the regular-approximability of a PFA has the nice consequence that its value can be effectively approximated, and the emptiness problem can be decided under the assumption of isolation.",
keywords = "Ambiguity, Probabilistic finite automata, Regular languages",
author = "Rohit Chadha and Sistla, \{A. Prasad\} and Mahesh Viswanathan",
note = "Publisher Copyright: {\textcopyright} Rohit Chadha, A. Prasad Sistla, and Mahesh Viswanathan; licensed under Creative Commons License CC-BY.; 27th Annual EACSL Conference Computer Science Logic, CSL 2018 ; Conference date: 04-09-2018 Through 07-09-2018",
year = "2018",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.CSL.2018.14",
language = "English (US)",
isbn = "9783959770880",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Ghica, \{Dan R.\} and Achim Jung",
booktitle = "Computer Science Logic 2018, CSL 2018",
}