Institut für Informatik und Computational Science
Refine
Has Fulltext
- no (1) (remove)
Year of publication
- 2020 (1) (remove)
Document Type
- Article (1)
Language
- English (1)
Is part of the Bibliography
- yes (1)
Keywords
- DNA hairpin formation (1) (remove)
Institute
This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed.