On iterated hairpin completion

DOI10.1016/j.tcs.2011.03.009zbMath1216.68145arXiv1010.3640OpenAlexW2018845878MaRDI QIDQ551189

Steffen Kopecki

Publication date: 14 July 2011

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

Full work available at URL: https://arxiv.org/abs/1010.3640

zbMATH Keywords

finite automataformal languageshairpin completionbounded hairpin completion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Iterated Hairpin Completions of Non-crossing Words ⋮ Hairpin Lengthening and Shortening of Regular Languages ⋮ IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR ⋮ Hairpin completions and reductions: semilinearity properties ⋮ Language theoretical properties of hairpin formations ⋮ The pseudopalindromic completion of regular languages ⋮ Further remarks on DNA overlap assembly ⋮ Regularity of Iterative Hairpin Completions of Crossing (2, 2)-Words ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ On the overlap assembly of strings and languages ⋮ State Complexity of Overlap Assembly

Cites Work

• Bounded hairpin completion
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• On some algorithmic problems regarding the hairpin completion
• The syntactic monoid of hairpin-free languages
• SOME REMARKS ON THE HAIRPIN COMPLETION
• On the Hairpin Completion of Regular Languages
• On the Iterated Hairpin Completion
• Bounded Hairpin Completion
• Hairpin Structures in DNA Words
• Hairpin Completion Versus Hairpin Reduction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item