Emptiness under isolation and the value problem for hierarchical probabilistic automata

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

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

Abstract

k-Hierarchical probabilistic automata (k-HPA) are probabilistic automata whose states are stratified into k + 1 levels such that from any state, on any input symbol, at most one successor belongs to the same level, while the remaining belong to higher levels. Our main result shows that the emptiness and universality problems are decidable for k-HPAs with isolated cut-points; recall that a cut-point x is isolated if the acceptance probability of every word is bounded away from x. Our algorithm for establishing this result relies on computing an approximation of the value of an HPA; the value of a probabilistic automaton is the supremum of the acceptance probabilities of all words. Computing the exact value of a probabilistic automaton is an equally important problem and we show that the problem is co-R.E.-complete for k-HPAs, for k ≥ 2 (as opposed to Π20-complete for general probabilistic automata). On the other hand, we also show that for 1-HPAs the value can be computed in exponential time.

Original languageEnglish (US)
Title of host publicationFoundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Proceedings
EditorsJavier Esparza, Andrzej S. Murawski
PublisherSpringer
Pages231-247
Number of pages17
ISBN (Print)9783662544570
DOIs
StatePublished - 2017
Event20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017 - Uppsala, Sweden
Duration: Apr 22 2017Apr 29 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10203 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017
CountrySweden
City Uppsala
Period4/22/174/29/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Emptiness under isolation and the value problem for hierarchical probabilistic automata'. Together they form a unique fingerprint.

Cite this