Decidable and expressive classes of probabilistic automata

Yue Ben, Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Contribution to journalArticlepeer-review

Abstract

k-Hierarchical probabilistic automata (HPA) are probabilistic automata whose states are partitioned into k+1 levels such that for any state and input symbol, at most one transition goes to a state at the same level, and others go to higher level states. We show that 1-HPA, with acceptance threshold 1/2 (in the finite and infinite word cases) can recognize non-regular languages, and the non-emptiness and non-universality problems for 1-HPA with threshold 1/2 are decidable in EXPTIME and are PSPACE-hard. We present a new sufficient condition when 1-HPA recognize regular languages. We show that the emptiness problem is undecidable for 2-HPAs.

Original languageEnglish (US)
Pages (from-to)70-95
Number of pages26
JournalJournal of Computer and System Sciences
Volume100
DOIs
StatePublished - Mar 2019

Keywords

  • Decidability
  • Emptiness problem
  • Hierarchical probabilistic automata
  • Regular languages
  • Universality problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Decidable and expressive classes of probabilistic automata'. Together they form a unique fingerprint.

Cite this