### 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 language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Andrew Pitts |

Publisher | Springer-Verlag Berlin Heidelberg |

Pages | 200-214 |

Number of pages | 15 |

ISBN (Print) | 9783662466773 |

DOIs | |

State | Published - Jan 1 2015 |

Event | 18th 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 2015 → Apr 18 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9034 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 18th 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 |
---|---|

Country | United Kingdom |

City | London |

Period | 4/11/15 → 4/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

*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