Article ID Journal Published Year Pages File Type
438519 Theoretical Computer Science 2007 16 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics