2026-07-22T12:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9681 2024-03-06T10:44:49Z ddc:004 open_access

Approximating Probabilistic Automata by Regular Languages Chadha, Rohit Sistla, A. Prasad Viswanathan, Mahesh Probabilistic Finite Automata Regular Languages Ambiguity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Chadha and A. Prasad Sistla and Mahesh Viswanathan 2018 Is Part Of LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2018.14 urn:nbn:de:0030-drops-96815 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.14 eng https://creativecommons.org/licenses/by/3.0/legalcode