On regularity of languages generated by copying systems

DOI10.1016/0166-218X(84)90129-XzbMath0549.68075OpenAlexW2022385202MaRDI QIDQ800098

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90129-x

zbMATH Keywords

regular languagescopy languagescopying systemsgenerative systemsrepetitions of subwords in words

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (13)

Tandem Duplications, Segmental Duplications and Deletions, and Their Applications ⋮ Languages generated by iterated idempotency ⋮ Well Quasi-orders in Formal Language Theory ⋮ On Regularity-Preservation by String-Rewriting Systems ⋮ On noncounting regular classes ⋮ On the regularity of languages on a binary alphabet generated by copying systems ⋮ General Idempotency Languages Over Small Alphabets ⋮ On the Prefix–Suffix Duplication Reduction ⋮ On Compensation Loops in Genomic Duplications ⋮ INNER PALINDROMIC CLOSURE ⋮ Watson–Crick Jumping Finite Automata ⋮ Computing the Tandem Duplication Distance is NP-Hard ⋮ The tandem duplication distance problem is hard over bounded alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Avoidable patterns in strings of symbols
• On the subword complexity of square-free DOL languages
• Sharp characterizations of squarefree morphisms
• On cube-free \(\omega\)-words generated by binary morphisms
• Uniformly growing k-th power-free homomorphisms
• Unending chess, symbolic dynamics and a problem in semi-groups
• Uniform tag sequences

This page was built for publication: On regularity of languages generated by copying systems