]>
The repository administrator has not yet configured an RDF license.
INVE_MEM_2014_174995.pdf
lightbox.jpg
preview.jpg
medium.jpg
small.jpg
indexcodes.txt
text/html
HTML Summary of #41500
Bounded prefix-suffix duplication
Bounded prefix-suffix duplication (PDF)
Bounded prefix-suffix duplication (Other)
Bounded prefix-suffix duplication (Other)
Bounded prefix-suffix duplication (Other)
Bounded prefix-suffix duplication (Other)
Bounded prefix-suffix duplication (Other)
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.
8587
2014
Bounded prefix-suffix duplication
Computer Science
InformÃ¡tica
19th International Conference, CIAA 2014 Giessen, Germany, July 30 â€“ August 2, 2014 : Proceedings
Giessen, Alemania
Springer
Dumitran
Marius
Marius Dumitran
Manea
Florin
Florin Manea
Gil Rubio
Francisco Javier
Francisco Javier Gil Rubio
Mitrana
Victor
Victor Mitrana