Reference:

Stefan Kiefer and Björn Wachter. Stability and complexity of minimising probabilistic automata. Technical report, arXiv.org, May 2014. Available at http://arxiv.org/abs/1404.6673.

Abstract:

We consider the state-minimisation problem for weighted and probabilistic automata. We provide a numerically stable polynomial-time minimisation algorithm for weighted automata, with guaranteed bounds on the numerical error when run with floating-point arithmetic. Our algorithm can also be used for lossy minimisation with bounded error. We show an application in image compression. In the second part of the paper we study the complexity of the minimisation problem for probabilistic automata. We prove that the problem is NP-hard and in PSPACE, improving a recent EXPTIME-result.

Suggested BibTeX entry:

@techreport{14KW-ICALP-TR,
    author = {Stefan Kiefer and Bj{\"o}rn Wachter},
    institution = {arXiv.org},
    month = {May},
    note = {Available at http://arxiv.org/abs/1404.6673},
    title = {Stability and Complexity of Minimising Probabilistic Automata},
    year = {2014}
}