Full text
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (851kB) | Preview |
Bounded prefix-suffix duplication
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.
Description
| Title: | Bounded prefix-suffix duplication |
|---|---|
| Author/s: |
|
| 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 |
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: | https://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-31... |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 09 Jun 2017 16:40 |
| Last Modified: | 09 Jun 2017 16:40 |
