کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438519 | 690285 | 2007 | 16 صفحه PDF | دانلود رایگان |

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.
Journal: Theoretical Computer Science - Volume 370, Issues 1–3, 12 February 2007, Pages 170-185