On the computation of some standard distances between probabilistic automata

Corinna Cortes, Mehryar Mohri, Ashish Rastogi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationImplementation and Application of Automata - 11th International Conference, CIAA 2006, Proceedings
PublisherSpringer Verlag
Pages137-149
Number of pages13
ISBN (Print)354037213X, 9783540372134
DOIs
StatePublished - 2006
Event11th International Conference on Implementation and Application of Automata, CIAA 2006 - Taipei, Taiwan, Province of China
Duration: Aug 21 2006Aug 23 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4094 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Conference on Implementation and Application of Automata, CIAA 2006
CountryTaiwan, Province of China
CityTaipei
Period8/21/068/23/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the computation of some standard distances between probabilistic automata'. Together they form a unique fingerprint.

Cite this