Low Disruption Transformations on Cyclic Automata

Abstract

We extend the edit operators of substitution, deletion, and insertion of a symbol over a word by introducing two new operators (partial copy and partial elimination) inspired by biological gene duplication. We define a disruption measure for an operator over a word and prove that whereas the traditional edit operators are disruptive, partial copy and partial elimination are non-disruptive. Moreover, we show that the application of only edit operators does not generate (with low disruption) all the words over a binary alphabet, but this can indeed be done by combining partial copy and partial elimination with the substitution operator.