Paper Info
Title
A disambiguation algorithm for weighted automata.
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 any weighted automaton over the tropical semiring for which the weighted determinization algorithm terminates and with any acyclic weighted automaton over an arbitrary weakly left divisible cancellative and commutative semiring. While disambiguation can sometimes be achieved using weighted 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.
Year
DOI
Venue
2017
10.1016/j.tcs.2016.08.019
Theoretical Computer Science
Keywords
Field
DocType
Weighted automata,Weighted automata algorithms,Automata theory,Rational power series
Discrete mathematics,Automata theory,Combinatorics,Deterministic automaton,Commutative property,Automaton,Correctness,Machine translation,Algorithm,Timed automaton,Mathematics,Semiring
Journal
Volume
ISSN
Citations 
679
0304-3975
0
PageRank 
References 
Authors
0.34
12
2
Name
Order
Citations
PageRank
Mehryar Mohri14502448.21
Michael Riley21027.13