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 -