State Complexity of Permutation on Finite Languages
Stefan Hoffmann · arXiv (Cornell University) · 2020
We investigate the state complexity of the permutation operation on finite languages. We give a tight bound that is expressed in terms of the longest strings in the unary projection languages. Moreover, we ask how large a minimal automaton could be for a finite language such that the lengths of the strings in the unary projection languages are bounded. Lastly, we look at a restricted class of languages with maximal state complexity and derive a state bound expressed in terms of the state complexity of the input language. This result fits with previous results on restricted classes for binary alphabets.