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 | |
State | Published - 11 Jan 2016 |
Keywords
- Finite automata
- Inversion operations
- Regular languages
- State complexity