TY - GEN
T1 - Approximating probabilistic automata by regular languages
AU - Chadha, Rohit
AU - Sistla, A. Prasad
AU - Viswanathan, Mahesh
N1 - Publisher Copyright:
© Rohit Chadha, A. Prasad Sistla, and Mahesh Viswanathan; licensed under Creative Commons License CC-BY.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - 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.
AB - 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.
KW - Ambiguity
KW - Probabilistic finite automata
KW - Regular languages
UR - http://www.scopus.com/inward/record.url?scp=85053061353&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85053061353&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CSL.2018.14
DO - 10.4230/LIPIcs.CSL.2018.14
M3 - Conference contribution
AN - SCOPUS:85053061353
SN - 9783959770880
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Computer Science Logic 2018, CSL 2018
A2 - Ghica, Dan R.
A2 - Jung, Achim
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th Annual EACSL Conference Computer Science Logic, CSL 2018
Y2 - 4 September 2018 through 7 September 2018
ER -