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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5722790 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 1241377 (Why is no real title available?)
- scientific article; zbMATH DE number 1342097 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- Bounded Hairpin Completion
- Bounded hairpin completion
- Hairpin Completion Versus Hairpin Reduction
- Hairpin Structures in DNA Words
- On some algorithmic problems regarding the hairpin completion
- On the Hairpin Completion of Regular Languages
- On the iterated hairpin completion
- Some remarks on the hairpin completion
- The syntactic monoid of hairpin-free languages
- Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
Cited in
(20)- On the iterated hairpin completion
- On the regularity of iterated hairpin completion of a single word
- Hairpin Lengthening and Shortening of Regular Languages
- Some remarks on the hairpin completion
- Some Remarks on Superposition Based on Watson-Crick-Like Complementarity
- On the hairpin incompletion
- Language theoretical properties of hairpin formations
- Bounded Hairpin Completion
- On some algorithmic problems regarding the hairpin completion
- State complexity of overlap assembly
- Iterated hairpin completions of non-crossing words
- Bounded hairpin completion
- A series of algorithmic results related to the iterated hairpin completion
- It is NL-complete to decide whether a hairpin completion of regular languages is regular
- Deciding regularity of hairpin completions of regular languages in polynomial time
- On the overlap assembly of strings and languages
- Further remarks on DNA overlap assembly
- Hairpin completions and reductions: semilinearity properties
- Regularity of iterative hairpin completions of crossing \((2, 2)\)-words
- The pseudopalindromic completion of regular languages
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)
