On the disambiguation of weighted automata

Mehryar Mohri, Michael D. Riley

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

Abstract

We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property. In particular, the algorithm can be used with all acyclic weighted automata and more generally any determinizable weighted automata. While disambiguation can sometimes be achieved using determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.

Original languageEnglish (US)
Title of host publicationImplementation and Application of Automata - 20th International Conference, CIAA 2015, Proceedings
EditorsFrank Drewes
PublisherSpringer Verlag
Pages263-278
Number of pages16
ISBN (Print)9783319223599
DOIs
StatePublished - 2015
Event20th International Conference on Implementation and Application of Automata, CIAA 2015 - Umea, Sweden
Duration: Aug 18 2015Aug 21 2015

Publication series

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

Other

Other20th International Conference on Implementation and Application of Automata, CIAA 2015
CountrySweden
CityUmea
Period8/18/158/21/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the disambiguation of weighted automata'. Together they form a unique fingerprint.

  • Cite this

    Mohri, M., & Riley, M. D. (2015). On the disambiguation of weighted automata. In F. Drewes (Ed.), Implementation and Application of Automata - 20th International Conference, CIAA 2015, Proceedings (pp. 263-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9223). Springer Verlag. https://doi.org/10.1007/978-3-319-22360-5_22