@inproceedings{09fc3d506ef64b98a9aaf7059c2cf6e1,
title = "State complexity of inversion operations",
abstract = "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.",
keywords = "Inversion operations, Regular languages, State complexity",
author = "Cho, {Da Jung} and Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",
year = "2014",
doi = "10.1007/978-3-319-09704-6_10",
language = "English",
isbn = "9783319097039",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "102--113",
booktitle = "Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Proceedings",
address = "Germany",
note = "16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014 ; Conference date: 05-08-2014 Through 08-08-2014",
}