Abstract
The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2n (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 uxRv such that uxv∈L (respectively, all strings uRx where ux∈L). We show that the nondeterministic state complexity of prefix-inversion is Θ(n2) and that of inversion is Θ(n3). We show that the deterministic state complexity of prefix-inversion is at most 2n⋅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)