Decidable and expressive classes of probabilistic automata

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

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

Abstract

Hierarchical probabilistic automata (HPA) are probabilistic automata whose states are partitioned into levels such that for any state and input symbol, at most one transition with non-zero probability goes to a state at the same level, and all others go to states at a higher level.We present expressiveness and decidability results for 1-level HPAs that work on both finite and infinite length input strings; in a 1-level HPA states are divided into only two levels (0 and 1). Our first result shows that 1-level HPAs, with acceptance threshold 1/2 (both in the finite and infinite word cases), can recognize non-regular languages. This result is surprising in the light of the following two facts. First, all earlier proofs demonstrating the recognition of non-regular languages by probabilistic automata employ either more complex automata or irrational acceptance thresholds or HPAs with more than two levels. Second, it has been previously shown that simple probabilistic automata (SPA), which are 1-level HPAs whose accepting states are all at level 0, recognize only regular languages. We show that even though 1-level HPAs with threshold 1/2 are very expressive (in that they recognize non-regular languages), the non-emptiness and non-universality problems are both decidable in EXPTIME. To the best our knowledge, this is the first such decidability result for any subclass of probabilistic automata that accept non-regular languages. We prove that these decision problems are also PSPACE-hard. Next, we present a new sufficient condition when 1-level HPAs recognize regular languages (in both the finite and infinite cases). Finally, we show that the emptiness and universality problems for this special class of HPAs is PSPACE-complete.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsAndrew Pitts
PublisherSpringer-Verlag Berlin Heidelberg
Pages200-214
Number of pages15
ISBN (Print)9783662466773
DOIs
StatePublished - Jan 1 2015
Event18th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2015 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015 - London, United Kingdom
Duration: Apr 11 2015Apr 18 2015

Publication series

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

Other

Other18th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2015 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015
CountryUnited Kingdom
CityLondon
Period4/11/154/18/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Chadha, R., Sistla, A. P., Viswanathan, M., & Ben, Y. (2015). Decidable and expressive classes of probabilistic automata. In A. Pitts (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 200-214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9034). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-662-46678-0_13