title: Bounded prefix-suffix duplication
creator: Gil Rubio, Francisco Javier
creator: Mitrana, Victor
creator: Dumitran, Marius
creator: Manea, Florin
subject: Computer Science
description: 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.
publisher: E.T.S.I de Sistemas Informáticos (UPM)
rights: https://creativecommons.org/licenses/by-nc-nd/3.0/es/
date: 2014
type: info:eu-repo/semantics/conferenceObject
type: Presentation at Congress or Conference
source: Implementation and application of automata : 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings | 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings | 30 de julio-2 de agosto de 2014 | Giessen, Alemania
type: PeerReviewed
format: application/pdf
language: eng
relation: https://link.springer.com/chapter/10.1007/978-3-319-08846-4_13
rights: info:eu-repo/semantics/openAccess
relation: info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-08846-4_13
identifier: https://oa.upm.es/41500/