On regularity of languages generated by copying systems
type: Item
instance of: scholarly article
title: On regularity of languages generated by copying systems
zbMATH Open document ID: 0549.68075
DOI: 10.1016/0166-218X(84)90129-X
author: Andrzej Ehrenfeucht
author: Grzegorz Rozenberg
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A new kind of generative systems, called copying systems, is introduced. These systems are meant to be useful in the study of repetitions of subwords in words, a research field generated by \textit{A. Thue} [Über unendliche Zeichenreihen, Norske Videnskaps, Selsk. Skr., I. Mat. Nat. Kl. Kristiania 7, 1-22 (1906)]. A copying system is defined as an ordered pair \(G=(\Sigma,w)\), where \(\Sigma\) is a finite alphabet and w is a nonempty word over \(\Sigma\). The language it generates is \(L(G)=\{x\in\Sigma^+| w copy^*x\},\) where \(copy^*\) is called the copying relation. It is defined as the reflexive and transitive closure of the direct copying relation over \(\sum^+:x copy y\) iff \(x=uzv\) and \(y=uzzv\), for some words u, v, z over \(\Sigma\), where z is nonempty. The paper contains a theorem allowing to prove that certain copy languages are not regular. A specific example is also provided. The authors point out two further problems of immediate interest: ''1) a characterization of regular copy languages, and 2) the relationship of copying systems to their ''symmetric version'' (that is introducing a square xx as well as reducing it to x are allowed).''
reviewed by: F.Petrescu
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3876629
zbMATH Keywords: regular languages
zbMATH Keywords: generative systems
zbMATH Keywords: copying systems
zbMATH Keywords: repetitions of subwords in words
zbMATH Keywords: copy languages
MaRDI profile type: Publication
cites work: Q3860007
cites work: Uniformly growing k-th power-free homomorphisms
cites work: Avoidable patterns in strings of symbols
cites work: Uniform tag sequences
cites work: Sharp characterizations of squarefree morphisms
cites work: Q3879325
cites work: On the subword complexity of square-free DOL languages
cites work: On cube-free \(\omega\)-words generated by binary morphisms
cites work: Unending chess, symbolic dynamics and a problem in semi-groups
cites work: Q3948608
full work available at URL: 0166-218x(84)90129-x
OpenAlex ID: W2022385202
description: scientific article; zbMATH DE number 3876629