Observatorio de I+D+i UPM

Memorias de investigación
Ponencias en congresos:
Hairpin Lengthening
Año:2010
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
The hairpin completion is a natural operation of formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. We consider here a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for practical 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. Although our motivation is based on biological phenomena, the present paper is more about some algorithmic properties of this operation. We prove that the iterated hairpin lengthening of a language recognizable in O(f(n)) time is recognizable in O(n2f(n)) time, while the one-step hairpin lengthening of such a language is recognizable in O(nf(n)) time. Finally, we propose an algorithm for computing the hairpin lengthening distance between two words in quadratic time.
Internacional
Si
Nombre congreso
6th Conference on Computability in Europe (CiE 2010)
Tipo de participación
960
Lugar del congreso
Univ Azores, Ponta Delgada, PORTUGAL
Revisores
Si
ISBN o ISSN
978-3-642-13961-1
DOI
Fecha inicio congreso
30/06/2010
Fecha fin congreso
04/07/2010
Desde la página
296
Hasta la página
306
Título de las actas
PROGRAMS, PROOFS, PROCESSES
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Computación Natural
S2i 2021 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)