Ricerc@Sapienza

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.