On the disambiguation of weighted automata

Mehryar Mohri, Michael D. Riley

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


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
Number of pages16
ISBN (Print)9783319223599
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other20th International Conference on Implementation and Application of Automata, CIAA 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this