Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

L_p DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA

CORINNA CORTES

Google Research, 76 Ninth Avenue, New York, NY 10011, USA

Search for more papers by this author

MEHRYAR MOHRI

Courant Institute of Mathematical Sciences and Google Research, 251 Mercer Street, New York, NY 10012, USA

Search for more papers by this author

, and

ASHISH RASTOGI

Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USA

Search for more papers by this author

https://doi.org/10.1142/S0129054107004966Cited by:16 (Source: Crossref)

Abstract

This paper presents an exhaustive analysis of the problem of computing the L_p distance of two probabilistic automata. It gives efficient exact and approximate algorithms for computing these distances for p even and proves the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. It further proves the hardness of approximating the L_p distance of two probabilistic automata for odd values of p. Similar techniques to those used for computing the L_p distance also yield efficient algorithms for computing the Hellinger distance of two unambiguous probabilistic automata both exactly and approximately.

A problem closely related to the computation of a distance between probabilistic automata is that of testing their equivalence. This paper also describes an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A₁ and A₂ in time O(|Σ|(|A₁| + |A₂|)³), a significant improvement over the previously best reported algorithm for this problem.

References

Kostyantyn Archangelsky, Efficient Algorithm for Checking Multiplicity Equivalence for the Finite Z – Σ*-Automata, Developments in Language Theory (DLT 2002) (2002) pp. 283–289. Google Scholar
Jean Berstel and Christophe Reutenauer , Rational Series and Their Languages ( Springer-Verlag , Berlin-New York , 1988 ) . Crossref, Google Scholar
Francisco Casacuberta and Colin De La Higuera, Computational complexity of problems on probabilistic grammars and transducers, Proceedings of the 5th International Colloquium on Grammatical Inference (ICGI 2000) (Springer-Verlag, 2000) pp. 15–24. Google Scholar
Corinna Cortes, Mehryar Mohri and Ashish Rastogi, On the Computation of Some Standard Distances between Probabilistic Automata, Proceedings of the 11th International Conference on Implementation and Application of Automata (CIAA 2006), Lecture Notes in Computer Science 4094 (Springer-Verlag, Heidelberg, Germany, 2006) pp. 137–149. Google Scholar
Corinna Corteset al., Efficient Computation of the Relative Entropy of Probabilistic Automata, Proceedings of LATIN 2006, LNCS 3887 (Springer-Verlag, 2006) pp. 323–336. Google Scholar
Corinna Corteset al., International Journal of Foundations of Computer Science (2007). Google Scholar
Imre Csiszar and Janos Korner , Information Theory: Coding Theorems for Discrete Memoryless Systems ( Akademiai Kiado , 1997 ) . Google Scholar
Karel Culik II and Jarkko Kari, Handbook of Formal Languages 3, eds. Grzegorz Rozenberg and Arto Salomaa (Springer, 1997) pp. 599–616. Crossref, Google Scholar
R. Durbin et al. , Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids ( Cambridge University Press , Cambridge UK , 1998 ) . Crossref, Google Scholar
Samuel Eilenberg , Automata, Languages and Machines A–B ( Academic Press , 1976 ) . Google Scholar
Lars Engebretsen and Jonas Holmerin, Clique is hard to approximate within n1−o(1), Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP 2000) (Springer-Verlag, 2000) pp. 2–12. Google Scholar
Joshua Goodman. Parsing inside-out. PhD thesis, Harvard University, May 1998 . Google Scholar
Werner Kuich and Arto Salomaa , Semirings, Automata, Languages , EATCS Monographs on Theoretical Computer Science 5 ( Springer-Verlag , Berlin, Germany , 1986 ) . Crossref, Google Scholar
Mehryar Mohri, Computational Linguistics 23(2), (1997). Google Scholar
Mehryar Mohri, International Journal of Foundations of Computer Science 13(1), 129 (2002), DOI: 10.1142/S0129054102000996. Link, Google Scholar
Mehryar Mohri, Journal of Automata, Languages and Combinatorics 7(3), 321 (2002). Web of Science, Google Scholar
Azaria Paz , Introduction to probabilistic automata ( Academic Press , New York , 1971 ) . Google Scholar
Michael O. Rabin, Information and Control 6, 230 (1963), DOI: 10.1016/S0019-9958(63)90290-0. Crossref, Google Scholar
Rune B. Lyngsø and Christian N. S. Pederson, Journal of Computer and System Sciences 65(3), 545 (2002). Crossref, Web of Science, Google Scholar
Arto Salomaa and Matti Soittola , Automata-Theoretic Aspects of Formal Power Series ( Springer-Verlag , 1978 ) . Crossref, Google Scholar
Marcel-Paul Schützenberger, Information and Control 4 (1961). Google Scholar
J. Håstad, Clique is hard to approximate within n1−∈, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996) (IEEE Computer Society, 1996) p. 627. Google Scholar
Flemming Topsøe, IEEE Trans. Inform. Theory 46, 1602 (2000). Crossref, Web of Science, Google Scholar
Wen-Guey Tzeng, A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata, Foundations of Computer Science (FOCS 1992) (1992) pp. 216–227. Google Scholar