Applications of Transducers in Independent Languages, Word Distances, Codes

A (nondeterministic) transducer $t$ is an operator mapping an input word to a set of possible output words. A few types of transducers are important in this work: input-altering, input-preserving, input-decreasing. For example, $t$ is input-altering, if no output word of $t$ is the same as the word that was used as input. Two words are $t$-dependent when one is the output of $t$ when the other is used as input. More general types of dependence via transducers are possible. We discuss how the above transducer types can provide elegant solutions to some cases of the following broad problems:

1. computing two minimum distance witness words of a given regular language,
2. computing witness words of non-satisfaction, or non-maximality, of a given regular language with respect to the independence specified by a given transducer,
3. computing, for any given $t$ and regular language $L$, a maximal $t$-independent language containing $L$.

The descriptional complexity cost of converting one type of transducer to another is discussed, when this conversion is possible.