
We consider a bio-inspired formal operation on words called prefix-suffix duplication which consists in the duplication of a prefix or suffix of a given word. The class of languages defined by the iterated application of the prefix-suffix duplication to a word is considered. We show that such a language is context-free if and only if the initial word contains just one letter. Moreover, every language in this class is semilinear and belongs to NL. We propose a 0(n2 logn) time and 0(n2 ) space recognition algorithm. Two algorithms are further proposed for computing the prefix-suffix duplication distance between two words, defined as the minimal number of prefix-suffix duplications applied to one of them in order to get the other one. The first algorithm runs in cubic time and uses quadratic space while the second one is more efficient, having 0(n2 logn) time complexity, but needs 0(n2 logn) space .
Informática, language-theoretical properties, Formal languages and automata, Algorithms on strings, Algorithms on words, Prefix-suffix duplication, prefix-suffix duplication distance, bio-inspired operations, Bio-inspired operations, Analysis of algorithms, Prefix-suffix duplication distance, prefix-suffix duplication, algorithms on words, Language theoretical properties
Informática, language-theoretical properties, Formal languages and automata, Algorithms on strings, Algorithms on words, Prefix-suffix duplication, prefix-suffix duplication distance, bio-inspired operations, Bio-inspired operations, Analysis of algorithms, Prefix-suffix duplication distance, prefix-suffix duplication, algorithms on words, Language theoretical properties
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
