Bounded prefix-suffix duplication

Gil Rubio, Francisco Javier and Mitrana, Victor and Dumitran, Marius and Manea, Florin (2014). Bounded prefix-suffix duplication. In: "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.

Description

Title: Bounded prefix-suffix duplication
Author/s:
  • Gil Rubio, Francisco Javier
  • Mitrana, Victor
  • Dumitran, Marius
  • Manea, Florin
Item Type: Presentation at Congress or Conference (Article)
Event Title: 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
Event Dates: 30 de julio-2 de agosto de 2014
Event Location: Giessen, Alemania
Title of Book: Implementation and application of automata : 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
Date: 2014
ISBN: 978-3-319-08845-7
Volume: 8587
Subjects:
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (851kB) | Preview

Abstract

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.

More information

Item ID: 41500
DC Identifier: http://oa.upm.es/41500/
OAI Identifier: oai:oa.upm.es:41500
DOI: 10.1007/978-3-319-08846-4_13
Official URL: https://link.springer.com/chapter/10.1007/978-3-319-08846-4_13
Deposited by: Memoria Investigacion
Deposited on: 09 Jun 2017 16:40
Last Modified: 09 Jun 2017 16:40
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM