Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438519 | Theoretical Computer Science | 2007 | 16 Pages |
Duplication languages are generated from an initial word by iterated application of string-rewriting rules of the form u→uu. In several recent articles such languages have been investigated with a main focus on finding their placement in the Chomsky hierarchy. We generalize the generating rules to um→un with arbitrary m and n.When the length of the factor u is a fixed number, most cases result in regular languages. If there is just some bound on the length, then often non-regular but always context-free languages are generated. The regularity conditions for both variants are fully characterized, and confluence for the underlying rewrite relations is determined. For the unrestricted case only some results are presented which carry over from restricted variants.