@inproceedings{76713d6972d84e8bb9522474538eebd8,

title = "On the computation of some standard distances between probabilistic automata",

abstract = "problem of the computation of a distance between two probabilistic automata arises in a variety of statistical learning problems. This paper presents an exhaustive analysis of the problem of computing the Lp distance between two automata. We give efficient exact and approximate algorithms for computing these distances for p even and prove the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. We also give an efficient algorithm for computing the Hellinger distance between unambiguous probabilistic automata. Our results include a general algorithm for the computation of the norm of an unambiguous probabilistic automaton based on a monoid morphism and efficient algorithms for the specific case of the computation of the Lp norm. Finally, we also describe an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A1 and A2 based on Schiitzenberger's standardization with a running time complexity of O(|Σ| (\A1\ + |A2|)3), a significant improvement over the previously best algorithm reported for this problem.",

author = "Corinna Cortes and Mehryar Mohri and Ashish Rastogi",

year = "2006",

doi = "10.1007/11812128_14",

language = "English (US)",

isbn = "354037213X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "137--149",

booktitle = "Implementation and Application of Automata - 11th International Conference, CIAA 2006, Proceedings",

note = "11th International Conference on Implementation and Application of Automata, CIAA 2006 ; Conference date: 21-08-2006 Through 23-08-2006",

}