On some algorithmic problems regarding the hairpin completion
From MaRDI portal
Publication:1026117
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
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