Hyper-minimisation of deterministic weighted finite automata over semifields.
Andreas Maletti, Daniel Quernheim · 2011
Hyper-minimisation of deterministic nite automata is a recently introduced state reduction technique that allows a nite change in the recognised language. A generalisation of this lossy compression method to the weighted setting over semi elds is presented, which allows the recognised formal power series to di er for nitely many input strings. First, the structure of hyper-minimal deterministic weighted nite automata is characterised in a similar way as in classical weighted minimisation and unweighted hyper-minimisation. Second, an e cient minimisation algorithm, which runs in time O(n logn), is derived from this characterisation.