Decidable and expressive classes of probabilistic automata

作者：

Highlights：

• Hierarchical Probabilsitic Automata with two levels (called 1-HPAs), can accept non-regular languages.

• Emptiness problem for 1-HPAs is decidable in EXPTIME and is PSPACE-hard.

• Presentation of an interesting subclass of 1-HPAs, called integer automata, that only accept regular languages, for which emptiness problem is PSPACE-complete.

• Emptiness problem for Hierarchical Probabilsitic Automata with three levels (denoted 2-HPAs), is undecidable.

摘要

•Hierarchical Probabilsitic Automata with two levels (called 1-HPAs), can accept non-regular languages.•Emptiness problem for 1-HPAs is decidable in EXPTIME and is PSPACE-hard.•Presentation of an interesting subclass of 1-HPAs, called integer automata, that only accept regular languages, for which emptiness problem is PSPACE-complete.•Emptiness problem for Hierarchical Probabilsitic Automata with three levels (denoted 2-HPAs), is undecidable.

论文关键词：Hierarchical probabilistic automata,Regular languages,Decidability,Emptiness problem,Universality problem

论文评审过程：Received 5 August 2016, Revised 7 February 2018, Accepted 11 September 2018, Available online 25 September 2018, Version of Record 19 November 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.09.002