Languages Generated by Iterated Idempotencies.

The rewrite relation with parameters m and n and with the possible length limit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. The idempotency languages generated from a starting word w by the respective operations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication have come up in different contexts. The investigations of Ito et al. about insertion and deletion, Le., operations that are also observed in DNA molecules, have established that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out from the case of a uniform length bound. For these relations =kW~ the conditions for confluence are characterized completely. Also the question of regularity is -k n answered for aH the languages w- D<lm . They are nearly always regular. Only the languages wD<lo for n > 1 are more complicated and belong to the class of context-free languages.For a generallength bound, i.e.'for the relations :'::kW~, confluence does not hold so frequently. This complicatedness of the relations results also in more complicated languages, which are often non-regular, as for example the languages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case of k :::; 3, though, remains open. We show, however, that none of these languages ever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicated structure. Over alphabets of one or two letters we still characterize the conditions for confluence. Over three or more letters, in contrast, only a few cases are solved. We determine the combinations of parameters that result in the regularity of wD