Observatorio de I+D+i UPM

Memorias de investigación
Other publications:
Deciding regularity of hairpin completions of regular languages in polynomial time
Year:2011
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
Entity
Cornell University Library
Place
USA
Pages
28
Reference/URL
http://arxiv.org/abs/1108.2427
Publication type
Research paper
Participants
  • Autor: Volker Diekert (University of Stuttgart, Germany)
  • Autor: Steffen Kopecki (University of Stuttgart, Germany)
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Organización y Estructura de la Información
  • Grupo de Investigación: Grupo de Computación Natural
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)