eprintid: 41500 rev_number: 7 eprint_status: archive userid: 1903 dir: disk0/00/04/15/00 datestamp: 2017-06-09 16:40:38 lastmod: 2017-06-09 16:40:38 status_changed: 2017-06-09 16:40:38 type: conference_item metadata_visibility: show creators_name: Gil Rubio, Francisco Javier creators_name: Mitrana, Victor creators_name: Dumitran, Marius creators_name: Manea, Florin creators_id: jgil@etsisi.upm.es creators_id: victor.mitrana@upm.es creators_id: dmarius1@yahoo.com creators_id: flm@informatik.uni-kiel.de title: Bounded prefix-suffix duplication ispublished: pub subjects: informatica 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. date: 2014 date_type: published publisher: Springer official_url: https://link.springer.com/chapter/10.1007/978-3-319-08846-4_13 id_number: 10.1007/978-3-319-08846-4_13 full_text_status: public pres_type: paper volume: 8587 place_of_pub: Cham (Suiza) pagerange: 176-187 event_title: 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings event_location: Giessen, Alemania event_dates: 30 de julio-2 de agosto de 2014 event_type: conference institution: ETSI_Sistemas_Infor department: Sistemas_informaticos_2014 refereed: TRUE isbn: 978-3-319-08845-7 book_title: Implementation and application of automata : 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings rights: by-nc-nd citation: 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 . document_url: https://oa.upm.es/41500/1/INVE_MEM_2014_174995.pdf