On some algorithmic problems regarding the hairpin completion

DOI10.1016/j.dam.2007.09.022zbMath1185.68392OpenAlexW2180809675MaRDI QIDQ1026117

Florin Manea, Carlos Martín-Vide, Victor Mitrana

Publication date: 24 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2007.09.022

zbMATH Keywords

membership problemhairpin completionhairpin completion distanceiterated hairpin completion

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

Iterated Hairpin Completions of Non-crossing Words ⋮ Hairpin Lengthening and Shortening of Regular Languages ⋮ A series of algorithmic results related to the iterated hairpin completion ⋮ Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions ⋮ 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 ⋮ On iterated hairpin completion ⋮ Bounded hairpin completion ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ Bounded Hairpin Completion ⋮ On the overlap assembly of strings and languages ⋮ State Complexity of Overlap Assembly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superposition based on Watson-Crick-like complementarity
• SOME REMARKS ON HAIRPIN AND LOOP LANGUAGES
• HAIRPIN LANGUAGES
• Developments in Language Theory
• Recognition and parsing of context-free languages in time n3

This page was built for publication: On some algorithmic problems regarding the hairpin completion