Operations on Permutation Automata

We investigate the class of languages recognized by permutation deterministic finite automata. Using automata constructions and some properties of permutation automata, we show that this class is closed under Boolean operations, reversal, and quotients, and it is not closed under concatenation, power, Kleene closure, positive closure, cut, shuffle, cyclic shift, and permutation. We prove that the state complexity of Boolean operations, Kleene closure, positive closure, and right quotient on permutation languages is the same as in the general case of regular languages. Next, we get the tight upper bounds on the state complexity of concatenation ([Formula: see text]), square ([Formula: see text]), reversal ([Formula: see text]), and left quotient ([Formula: see text]; tight if [Formula: see text]). All our witnesses are unary or binary, and the binary alphabet is always optimal, except for Boolean operations in the case of [Formula: see text]. In the unary case, the state complexity of all considered operations is the same as for regular languages, except for quotients and cut. In case of quotients, it is [Formula: see text], and in case of cut, it is either [Formula: see text] or [Formula: see text], depending on whether there exists an integer [Formula: see text] with [Formula: see text] such that [Formula: see text].