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 language | English (US) |
|---|---|
| Pages (from-to) | 70-95 |
| Number of pages | 26 |
| Journal | Journal of Computer and System Sciences |
| Volume | 100 |
| DOIs | |
| State | Published - Mar 2019 |
Keywords
- Decidability
- Emptiness problem
- Hierarchical probabilistic automata
- Regular languages
- Universality problem
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Applied Mathematics
- Computer Networks and Communications
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'Decidable and expressive classes of probabilistic automata'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS