State complexity of inversion operations

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


The reversal operation is well-studied in 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 of a language L consists of all strings uxR v such that uxv ∈ L. We show that the nondeterministic state complexity of inversion is in Θ(n 3). We establish that the deterministic state complexity of the inversion is 2Ω(n·logn), which is strictly worse than the worst case state complexity of the reversal operation. We also study the state complexity of different variants of the inversion operation, including prefix-, suffix-, and pseudo-inversion.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319097039
StatePublished - 2014
Event16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014 - Turku, Finland
Duration: 5 Aug 20148 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8614 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014


  • Inversion operations
  • Regular languages
  • State complexity


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

Cite this