Paper Info
Title
On the computation of some standard distances between probabilistic automata
Abstract
The 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 Schützenberger’s standardization with a running time complexity of O(|Σ| (|A1| + |A2|)3), a significant improvement over the previously best algorithm reported for this problem.
Year
DOI
Venue
2006
10.1007/11812128_14
CIAA
Keywords
Field
DocType
standard distance,hellinger distance,general algorithm,best algorithm,arbitrary probabilistic automaton,statistical learning problem,probabilistic automaton,unambiguous probabilistic automaton,lp distance,approximate algorithm,efficient algorithm,time complexity,lp norm,probabilistic automata,generic algorithm
Discrete mathematics,Quantum finite automata,Hellinger distance,Algorithm,Probabilistic CTL,Probabilistic analysis of algorithms,Linear programming,Time complexity,Probabilistic automaton,Mathematics,Computation
Conference
Volume
ISSN
ISBN
4094
0302-9743
3-540-37213-X
Citations 
PageRank 
References 
9
0.62
9
Authors
3
Name
Order
Citations
PageRank
Corinna Cortes165741120.50
Mehryar Mohri24502448.21
Ashish Rastogi316110.55