Further Properties of Self-assembly by Hairpin Formation

Bordihn, Henning and Mitrana, Victor and Paun, Paul Andrei and Paun, Mihaela (2019). Further Properties of Self-assembly by Hairpin Formation. In: "18th International Conference on Unconventional Computation and Natural Computation, UCNC 2019", 03/06/2019-07/06/2019, Tokio, Japón. ISBN 978-3-030-19310-2. pp. 37-51. https://doi.org/10.1007/978-3-030-19311-9_5.

Description

Title: Further Properties of Self-assembly by Hairpin Formation
Author/s:
  • Bordihn, Henning
  • Mitrana, Victor
  • Paun, Paul Andrei
  • Paun, Mihaela
Item Type: Presentation at Congress or Conference (Article)
Event Title: 18th International Conference on Unconventional Computation and Natural Computation, UCNC 2019
Event Dates: 03/06/2019-07/06/2019
Event Location: Tokio, Japón
Title of Book: Unconventional Computation and Natural Computation
Date: 26 April 2019
ISBN: 978-3-030-19310-2
Subjects:
Freetext Keywords: DNA hairpin formation; Hairpin completion; Bounded hairpin completion; Hairpin lengthening; Semilinearity property
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (195kB) | Preview

Abstract

We continue the investigation of three operations on words and languages with motivations coming from DNA biochemistry, namely unbounded and bounded hairpin completion and hairpin lengthening. We first show that each of these operations can be used for replacing the third step, the most laborious one, of the solution to the CNF-SAT reported in [28]. As not all the bounded/unbounded hairpin completionor lengthening of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying once either the bounded or unbounded hairpin completion, or lengthening. A similar approach is then started for theiterated variants of the three operations. A few open problems are finally discussed.

Funding Projects

TypeCodeAcronymLeaderTitle
UnspecifiedPOC P-37-257UnspecifiedRomanian National Authority for Scientific Research and InnovationUnspecified

More information

Item ID: 65196
DC Identifier: https://oa.upm.es/65196/
OAI Identifier: oai:oa.upm.es:65196
DOI: 10.1007/978-3-030-19311-9_5
Official URL: http://www.ucnc2019.uec.ac.jp/#:~:text=The%20International%20Conference%20on%20Unconventional,computational%20aspects%20of%20natural%20processes.
Deposited by: Memoria Investigacion
Deposited on: 29 Jan 2021 15:22
Last Modified: 29 Jan 2021 15:22
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM