Observatorio de I+D+i UPM

Memorias de investigación
Otras publicaciones:
Deciding regularity of hairpin completions of regular languages in polynomial time
Año:2011
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
The hairpin completion is an operation on formal languages that has been inspired by the hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the hairpin completion of regular languages. It is well known that hairpin completions of regular languages are linear context-free and not necessarily regular. As regularity of a (linear) context-free language is not decidable, the question arose whether regularity of a hairpin completion of regular languages is decidable. We prove that this problem is decidable and we provide a polynomial time algorithm. Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language and, as such, it has an effectively computable growth function. Moreover, we show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential and, in case the hairpin completion is regular, then the hairpin completion and the underlying languages have the same growth indicator.
Internacional
Si
Entidad
Cornell University Library
Lugar
USA
Páginas
28
Referencia/URL
http://arxiv.org/abs/1108.2427
Tipo de publicación
Research paper
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Volker Diekert (University of Stuttgart, Germany)
  • Autor: Steffen Kopecki (University of Stuttgart, Germany)
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Organización y Estructura de la Información
  • 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)