On the regularity of languages on a binary alphabet generated by copying systems

DOI10.1016/0020-0190(92)90050-6zbMath0759.68049OpenAlexW2056860821WikidataQ127310084 ScholiaQ127310084MaRDI QIDQ1205714

Stefano Varricchio, Daniel P. Bovet

Publication date: 1 April 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90050-6

zbMATH Keywords

copying systemswell quasi orders

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (14)

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 ⋮ Prefix-suffix duplication ⋮ General Idempotency Languages Over Small Alphabets ⋮ Well quasi-orders and context-free grammars ⋮ Stefano Varricchio (1960-2008) ⋮ On the Prefix–Suffix Duplication Reduction ⋮ On Compensation Loops in Genomic Duplications ⋮ INNER PALINDROMIC CLOSURE ⋮ Well quasi-orders, unavoidable sets, and derivation systems ⋮ Computing the Tandem Duplication Distance is NP-Hard ⋮ The tandem duplication distance problem is hard over bounded alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• On regularity of context-free languages
• On regularity of languages generated by copying systems
• Ordering by Divisibility in Abstract Algebras

This page was built for publication: On the regularity of languages on a binary alphabet generated by copying systems