State complexity of inversion operations

The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2n2n (respectively, n). We consider the inversion operation where some substring of the given string is reversed. Formally, the inversion (respectively, prefix-inversion) of a language L   consists of all strings uxRvuxRv such that uxv∈Luxv∈L (respectively, all strings uRxuRx where ux∈Lux∈L). We show that the nondeterministic state complexity of prefix-inversion is Θ(n2)Θ(n2) and that of inversion is Θ(n3)Θ(n3). We show that the deterministic state complexity of prefix-inversion is at most 2n⋅log⁡n+n2n⋅log⁡n+n and has lower bound 2Ω(nlog⁡n)2Ω(nlog⁡n). The same lower bound holds for the state complexity of inversion, but for inversion we do not have a matching upper bound. We also study the state complexity of other variants of the inversion operation.