most citedLinear-Space Computation of the Edit-Distance between a String and a Finite Automaton

15 citations · 15 across the 3 of their papers we have counts for

collaborators
Showing cs.CCShow all

2 papers · 1 filter

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…