RAIRO - Theoretical Informatics and Applications · 2008 · 35 citations · 25 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationAutomata TheoryFinite AutomataFinite-state MachinesAutomata-theoretic CharacterizationsFinite Automata TheoryState ComplexityWeighted AutomataWeighted Finite-state Automata
We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
25
Finite-state transducers in language and speech processing
Mehryar Mohri · 1997 · 922 citations
Image compression using weighted finite automata
Karel Čulík, Jarkko Kari · Computers & Graphics · 1993 · 125 citations
Factorization forests of finite height
Imre Simon · Theoretical Computer Science · 1990 · 124 citations