On implementing recognizable transductions

Abstract

Recognizable transductions constitute a proper subclass of rational transductions, characterized by the well-known Mezei's Theorem. We propose a family of transducers which reflect accurately this characterization, and we study their properties and their algorithmic aspects. We base our construct on the observation 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 accepts all possible edit strings corresponding to each accepted pair of words, when viewed as an automaton over the edit alphabet. We revisit the theory behind recognizable transductions from the point of view of saturated transducers, and we give constructive proofs as well as descriptional complexities for their closure properties. In particular, we give a novel and rather non-trivial algorithm for constructing a saturated transducer for the concatenation of two saturated transductions. Finally, we discuss the natural role of these objects in edit distance problems. Perhaps the relevance of this work lies more in its point of view and initiative rather than in any particular result.

Keywords:

• transducer
• recognizable transduction
• saturated transducer
• edit string
• edit language
• edit distance

2000 AMS Subject Classification :

• 68Q70
• 68Q19
• 68Q45
• 68Q42
• 68P30

Acknowledgements

This work was supported by the Natural Science and Engineering Research Council of Canada grants R220259 and OGP0041630.