Paper Info
Title
Stability and Complexity of Minimising Probabilistic Automata.
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.
Year
DOI
Venue
2014
10.1007/978-3-662-43951-7_23
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8573
0302-9743
Citations 
PageRank 
References 
4
0.42
13
Authors
2
Name
Order
Citations
PageRank
Stefan Kiefer134536.87
Björn Wachter232620.09