On some algorithmic problems regarding the hairpin completion

DOI10.1016/j.dam.2007.09.022zbMath1185.68392MaRDI 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 problem; hairpin completion; hairpin completion distance; iterated hairpin completion

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions, Regularity of Iterative Hairpin Completions of Crossing (2, 2)-Words, State Complexity of Overlap Assembly, Hairpin completions and reductions: semilinearity properties, Language theoretical properties of hairpin formations, The pseudopalindromic completion of regular languages, Further remarks on DNA overlap assembly, On iterated hairpin completion, Bounded hairpin completion, A series of algorithmic results related to the iterated hairpin completion, Deciding regularity of hairpin completions of regular languages in polynomial time, On the overlap assembly of strings and languages, 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, Bounded Hairpin Completion

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