We consider a family of new formal operation on words: the prefix square completion, the suffix square completion, and the prefix-suffix square completion. By suffix square completion (respectively, prefix square completion), one can derive from a word w any word wx (respectively, xw) if w has a suffix (respectively, prefix) yxy; by prefix-suffix square completion we derive from a word w any word w' that is obtained either by prefix square completion or by suffix square completion from w. We discuss two main aspects of these operations. On the one hand, we study the derivation of infinite words by iterated prefix-suffix square completion, and show that, although any word generated by square completion operations contains squares, we can generate infinite words that do not contain any repetition of exponent greater than 2. On the other hand, focusing on finite words, we give a linear time procedure that, given two words, decides whether the longer can be generated by iterated prefix-suffix square completion from the shorter.
['Marius Dumitran', 'Florin Manea']
Prefix-Suffix Square Completion