## Abstract

The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2^{n} (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 ux^{R}v such that uxv∈L (respectively, all strings u^{R}x where ux∈L). We show that the nondeterministic state complexity of prefix-inversion is Θ(n^{2}) and that of inversion is Θ(n^{3}). We show that the deterministic state complexity of prefix-inversion is at most 2^{n⋅logn+n} and has lower bound 2^{Ω(nlogn)}. 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.

Original language | English |
---|---|

Pages (from-to) | 2-12 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 610 |

DOIs | |

Publication status | Published - 2016 Jan 11 |

### Bibliographical note

Funding Information:Cho, Han and Ko were supported by the Basic Science Research Program through NRF funded by MEST ( 2012R1A1A2044562 ), the International Cooperation Program managed by NRF of Korea ( 2014K2A1A2048512 ) and the Yonsei University Future-leading Research Initiative of 2014. Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224 .

Funding Information:

Cho, Han and Ko were supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512) and the Yonsei University Future-leading Research Initiative of 2014. Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Publisher Copyright:

© 2015 Elsevier B.V.

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)