2 papers
cs.CC2008
General Algorithms for Testing the Ambiguity of Finite Automata
Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with -transitions. It gives an algorithm for testing th…
cs.CC2008
3-Way Composition of Weighted Finite-State Transducers
Cyril Allauzen, Mehryar Mohri
Composition of weighted transducers is a fundamental algorithm used in many applications, including for computing complex edit-distances between automata, or string kernels in mach…