Language theoretical properties of hairpin formations

DOI10.1016/j.tcs.2011.12.025zbMath1260.68200MaRDI QIDQ418760

Volker Diekert, Steffen Kopecki

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.025

zbMATH Keywords

varieties; regular languages; hairpin completion; hairpin lengthening

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q42: Grammars and rewriting systems

Related Items

Deciding regularity of hairpin completions of regular languages in polynomial time, Hairpin Lengthening and Shortening of Regular Languages

Cites Work

• On iterated hairpin completion
• A series of algorithmic results related to the iterated hairpin completion
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• On some algorithmic problems regarding the hairpin completion
• SOME REMARKS ON THE HAIRPIN COMPLETION
• On the Hairpin Incompletion
• Hairpin Lengthening and Shortening of Regular Languages
• On the Hairpin Completion of Regular Languages
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Hairpin Lengthening
• Around Dot Depth Two
• THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• Hairpin Completion Versus Hairpin Reduction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item