Approximating probabilistic automata by regular languages

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationComputer Science Logic 2018, CSL 2018
EditorsDan R. Ghica, Achim Jung
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770880
DOIs
StatePublished - Aug 1 2018
Event27th Annual EACSL Conference Computer Science Logic, CSL 2018 - Birmingham, United Kingdom
Duration: Sep 4 2018Sep 7 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume119
ISSN (Print)1868-8969

Other

Other27th Annual EACSL Conference Computer Science Logic, CSL 2018
Country/TerritoryUnited Kingdom
CityBirmingham
Period9/4/189/7/18

Keywords

  • Ambiguity
  • Probabilistic finite automata
  • Regular languages

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Approximating probabilistic automata by regular languages'. Together they form a unique fingerprint.

Cite this