Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Hairpin lengthening: language theoretic and algorithmic results
Year:2015
Research Areas
  • Information technology and adata processing
Information
Abstract
The hairpin completion is a newly introduced operation on formal languages, inspired by biological phenomena and by DNAcomputing. In this article, we analyse a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for a possible bio-lab implementation. The variant considered here concerns the lengthening of the word that forms a hairpin structure, such that this structure is preserved, without necessarily completing the hairpin. First we present a series of language theoretic results regarding the one-step and iterated hairpin lengthening of languages from different classes of the Chomsky hierarchy. Following our biological motivation we also approach several algorithmic properties of this operation. More precisely, we propose an efficient algorithm for the recognition of the iterated hairpin lengthening of a language, and show how it can be particularized to recognize the one-step hairpin lengthening of a language; the cases when the starting language is finite, regular, linear context-free or context-free are discussed. It is worth noting that these results cannot be deduced canonically from the closure properties of the discussed classes of languages.We also propose an algorithm for computing efficiently the hairpin lengthening distance between a word and all its factors; this algorithm can be used to compute the distance between two words, or the common hairpin-lengthening ancestors of two words.
International
Si
JCR
Si
Title
Journal of Logic And Computation
ISBN
0955-792X
Impact factor JCR
0,504
Impact info
Volume
25
10.1093/logcom/exs076
Journal number
4
From page
987
To page
1009
Month
AGOSTO
Ranking
Participants
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Modelización Matemática y Biocomputación
  • Departamento: Sistemas Informáticos
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)