Bounded prefix-suffix duplication

Gil Rubio, Francisco Javier; Mitrana, Victor; Dumitran, Marius y Manea, Florin (2014). Bounded prefix-suffix duplication. En: "19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings", 30 de julio-2 de agosto de 2014, Giessen, Alemania. ISBN 978-3-319-08845-7. pp. 176-187. https://doi.org/10.1007/978-3-319-08846-4_13.

Descripción

Título: Bounded prefix-suffix duplication
Autor/es:
  • Gil Rubio, Francisco Javier
  • Mitrana, Victor
  • Dumitran, Marius
  • Manea, Florin
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
Fechas del Evento: 30 de julio-2 de agosto de 2014
Lugar del Evento: Giessen, Alemania
Título del Libro: Implementation and application of automata : 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
Fecha: 2014
ISBN: 978-3-319-08845-7
Volumen: 8587
Materias:
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (851kB) | Vista Previa

Resumen

We consider a restricted variant of the prefix-suffix duplication operation, called bounded prefix-suffix duplication. It consists in the iterative duplication of a prefix or suffix, whose length is bounded by a constant, of a given word. We give a sufficient condition for the closure under bounded prefix-suffix duplication of a class of languages. Consequently, the class of regular languages is closed under bounded prefix-suffix duplication; furthermore, we propose an algorithm deciding whether a regular language is a finite k-prefix-suffix duplication language. An efficient algorithm solving the membership problem for the k-prefix-suffix duplication of a language is also presented. Finally, we define the k-prefix-suffix duplication distance between two words, extend it to languages and show how it can be computed for regular languages.

Más información

ID de Registro: 41500
Identificador DC: http://oa.upm.es/41500/
Identificador OAI: oai:oa.upm.es:41500
Identificador DOI: 10.1007/978-3-319-08846-4_13
URL Oficial: https://link.springer.com/chapter/10.1007/978-3-319-08846-4_13
Depositado por: Memoria Investigacion
Depositado el: 09 Jun 2017 16:40
Ultima Modificación: 09 Jun 2017 16:40
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM