State complexity of inversion operations

Da Jung Cho, Yo Sub Han, Sang Ki Ko, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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⋅log⁡n+n and has lower bound 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.

Original languageEnglish
Pages (from-to)2-12
Number of pages11
JournalTheoretical Computer Science
Volume610
DOIs
StatePublished - 11 Jan 2016

Keywords

  • Finite automata
  • Inversion operations
  • Regular languages
  • State complexity

Fingerprint

Dive into the research topics of 'State complexity of inversion operations'. Together they form a unique fingerprint.

Cite this