Hairpin completions and reductions
- 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.
| Author details: | Henning BordihnORCiD, Victor MitranaORCiDGND, Andrei PaunORCiD, Mihaela PaunORCiD |
|---|---|
| DOI: | https://doi.org/10.1007/s11047-020-09797-0 |
| ISSN: | 1572-9796 |
| Title of parent work (English): | Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal |
| Subtitle (English): | semilinearity properties |
| Publisher: | Springer Science + Business Media B.V. |
| Place of publishing: | Dordrecht |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2020/06/27 |
| Publication year: | 2020 |
| Release date: | 2023/10/10 |
| Tag: | DNA hairpin formation; Hairpin completions; Hairpin reductions; Semilinearity property |
| Volume: | 20 |
| Issue: | 2 |
| Number of pages: | 11 |
| First page: | 193 |
| Last Page: | 203 |
| Funding institution: | Romanian National Authority for Scientific Research and Innovation [POC; P-37-257]; Alexander von Humboldt FoundationAlexander von Humboldt; Foundation |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer review: | Referiert |
