Prefix-suffix square reduction
In this work we introduce the operations of unbounded and bounded prefix-suffix square reduction. We show that, in general, the time complexity of the unbounded prefix-suffix square reduction of a language increases by an n factor in comparison to the complexity of the given language. This factor is just the bound in the case of bounded prefix-suffix square reduction and is not necessary for regular languages. As a consequence, the class of regular languages is closed under unbounded and bounded prefix-suffix square reduction.
We show that the class of regular languages is still closed under iterated bounded prefix-suffix square reduction, but the unbounded case remains open. We also show that there are linear languages such that their iterated unbounded prefix-suffix square reduction is not context-free and one cannot algorithmically decide when this is the case. Afterwards, we define the primitive prefix-suffix square root of a word w as a word x that can be obtained from w by iterated prefix-suffix square reductions and is irreducible, i.e., no further prefix or suffix square reduction can be applied.
We prove that the language of primitive prefix-suffix square roots of all words over an alphabet is never regular for alphabets with at least two symbols in the unbounded case, and always regular in the bounded case. The papers ends with a brief discussion on some open problems and some algorithmic aspects.