We consider the embedding problem in coding theory: given an independence (a code-related property) and an independent language $L$, find a maximal independent language containing $L$. We solve the problem by providing an embedding formula for the case where the code-related property is defined via a rational binary relation that is decreasing with respect to any fixed total order on the set of words. Our method works by iterating a max-min operator that has been used before for the embedding problem for properties defined by length-increasing-and-transitive binary relations. We use input-decreasing transducers to represent order-decreasing rational relations, and we show that these transducers can describe many known properties from both the noiseless and noisy domains of coding theory, as well as  any combination of such properties. Moreover, in many cases the desired maximal embedding is effectively computable. Finally, we show that there is no embedding formula when the given code-related property is defined via an input-altering transducer.

Keywords: languages; maximal codes; embedding; variable-length codes; transducers; error control codes

About the speaker: Stavros Konstantinidis is a full professor at the  Department of Mathematics and Computing Science, Saint Mary's University, Halifax, NS, Canada. His research activities concerns code and automata theory, with special interest in independence, automata algorithms  and descriptional complexity of formal languages with applications to DNA computing.