On iterated hairpin completion

DOI10.1016/J.TCS.2011.03.009zbMATH Open1216.68145arXiv1010.3640OpenAlexW2018845878MaRDI QIDQ551189FDOQ551189

Authors: Steffen Kopecki 

Publication date: 14 July 2011

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

Abstract: The (bounded) hairpin completion and its iterated versions are operations on formal lan- guages which have been inspired by the hairpin formation in DNA-biochemistry. The paper answers two questions asked in the literature about the iterated hairpin completion. The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all the classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion. In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular, actually it is not context-free, but context-sensitive.

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

Recommendations

• On the iterated hairpin completion
• Some remarks on the hairpin completion
• On the regularity of iterated hairpin completion of a single word
• Iterated hairpin completions of non-crossing words
• Regularity of iterative hairpin completions of crossing \((2, 2)\)-words

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The syntactic monoid of hairpin-free languages
• 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 Completion of Regular Languages
• Title not available (Why is that?)
• Hairpin Completion Versus Hairpin Reduction
• Bounded hairpin completion
• On the iterated hairpin completion
• Bounded Hairpin Completion
• Hairpin Structures in DNA Words
• Title not available (Why is that?)

Cited In (20)

• Language theoretical properties of hairpin formations
• A series of algorithmic results related to the iterated hairpin completion
• Deciding regularity of hairpin completions of regular languages in polynomial time
• On some algorithmic problems regarding the hairpin completion
• State complexity of overlap assembly
• On the iterated hairpin completion
• Some remarks on the hairpin completion
• On the hairpin incompletion
• It is NL-complete to decide whether a hairpin completion of regular languages is regular
• Hairpin completions and reductions: semilinearity properties
• Some Remarks on Superposition Based on Watson-Crick-Like Complementarity
• The pseudopalindromic completion of regular languages
• Bounded hairpin completion
• Hairpin Lengthening and Shortening of Regular Languages
• On the overlap assembly of strings and languages
• On the regularity of iterated hairpin completion of a single word
• Bounded Hairpin Completion
• Iterated hairpin completions of non-crossing words
• Further remarks on DNA overlap assembly
• Regularity of iterative hairpin completions of crossing \((2, 2)\)-words

This page was built for publication: On iterated hairpin completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551189)