Decidable and expressive classes of probabilistic automata

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

Research output: Contribution to journalArticle

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

Fingerprint

Probabilistic Automata
Formal languages
Infinite Words
Regular Languages
Class
Sufficient Conditions

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

Cite this

Decidable and expressive classes of probabilistic automata. / Ben, Yue; Chadha, Rohit; Sistla, A. Prasad; Viswanathan, Mahesh.

In: Journal of Computer and System Sciences, Vol. 100, 03.2019, p. 70-95.

Research output: Contribution to journalArticle

Ben, Yue ; Chadha, Rohit ; Sistla, A. Prasad ; Viswanathan, Mahesh. / Decidable and expressive classes of probabilistic automata. In: Journal of Computer and System Sciences. 2019 ; Vol. 100. pp. 70-95.
@article{469ad5d445f14f2cb04301c3a9761acb,
title = "Decidable and expressive classes of probabilistic automata",
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.",
keywords = "Decidability, Emptiness problem, Hierarchical probabilistic automata, Regular languages, Universality problem",
author = "Yue Ben and Rohit Chadha and Sistla, {A. Prasad} and Mahesh Viswanathan",
year = "2019",
month = "3",
doi = "10.1016/j.jcss.2018.09.002",
language = "English (US)",
volume = "100",
pages = "70--95",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Decidable and expressive classes of probabilistic automata

AU - Ben, Yue

AU - Chadha, Rohit

AU - Sistla, A. Prasad

AU - Viswanathan, Mahesh

PY - 2019/3

Y1 - 2019/3

N2 - 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.

AB - 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.

KW - Decidability

KW - Emptiness problem

KW - Hierarchical probabilistic automata

KW - Regular languages

KW - Universality problem

UR - http://www.scopus.com/inward/record.url?scp=85054560166&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054560166&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2018.09.002

DO - 10.1016/j.jcss.2018.09.002

M3 - Article

AN - SCOPUS:85054560166

VL - 100

SP - 70

EP - 95

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -