Reference:

Stefan Kiefer and Björn Wachter. Stability and complexity of minimising probabilistic automata. In J. Esparza et al., editor, Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), part II, volume 8573 of LNCS, pages 268–279, Copenhagen, Denmark, 2014. Springer.

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:

@inproceedings{14KW-ICALP,
    address = {Copenhagen, Denmark},
    author = {Stefan Kiefer and Bj{\"o}rn Wachter},
    booktitle = {Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), part II},
    editor = {J. Esparza et al.},
    pages = {268--279},
    publisher = {Springer},
    series = {LNCS},
    title = {Stability and Complexity of Minimising Probabilistic Automata},
    volume = {8573},
    year = {2014}
}