TY - GEN
T1 - On the disambiguation of weighted automata
AU - Mohri, Mehryar
AU - Riley, Michael D.
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84951765310&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951765310&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-22360-5_22
DO - 10.1007/978-3-319-22360-5_22
M3 - Conference contribution
AN - SCOPUS:84951765310
SN - 9783319223599
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 263
EP - 278
BT - Implementation and Application of Automata - 20th International Conference, CIAA 2015, Proceedings
A2 - Drewes, Frank
PB - Springer Verlag
T2 - 20th International Conference on Implementation and Application of Automata, CIAA 2015
Y2 - 18 August 2015 through 21 August 2015
ER -