Recognizable Transductions, Saturated Transducers and Edit Languages

        Stavros Konstantinidis, Nicolae Santean and Sheng Yu

Recognizable transductions constitute a well known, proper subclass of 
rational transductions. To our knowledge, there has been no characterization 
of recognizable transductions by a well-defined subclass of transducers. 
In this work we observe that there is a connection between recognizable
transductions and languages consisting of edit strings. More
specifically, we define a saturated transducer to be a transducer
with the property that, for every pair of words it realizes, the
transducer, when viewed as an automaton over the edit alphabet,
accepts all possible edit strings transforming the first word of the
pair into the second one. Our main result is a constructive proof
that the class of recognizable transductions coincides with the
class of saturated transductions. We also revisit closure properties of
recognizable transductions using saturated transducers and discuss the
natural role of these objects in edit distance problems.