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.
| Verfasserangaben: | Henning BordihnORCiD, Victor MitranaORCiDGND, Andrei PaunORCiD, Mihaela PaunORCiD |
|---|---|
| DOI: | https://doi.org/10.1007/s11047-020-09797-0 |
| ISSN: | 1572-9796 |
| Titel des übergeordneten Werks (Englisch): | Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal |
| Untertitel (Englisch): | semilinearity properties |
| Verlag: | Springer Science + Business Media B.V. |
| Verlagsort: | Dordrecht |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Erstveröffentlichung: | 27.06.2020 |
| Erscheinungsjahr: | 2020 |
| Datum der Freischaltung: | 10.10.2023 |
| Freies Schlagwort / Tag: | DNA hairpin formation; Hairpin completions; Hairpin reductions; Semilinearity property |
| Band: | 20 |
| Ausgabe: | 2 |
| Seitenanzahl: | 11 |
| Erste Seite: | 193 |
| Letzte Seite: | 203 |
| Fördernde Institution: | Romanian National Authority for Scientific Research and Innovation [POC; P-37-257]; Alexander von Humboldt FoundationAlexander von Humboldt; Foundation |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer Review: | Referiert |
