\subsection{Projections of Commutative Languages}

\begin{lemma} 
\label{lem:centralizer}
 Suppose $\mathcal A = (Q, \Sigma, \delta, q_0, F)$
 is an arbitrary DFA.
 Let $\Gamma \subseteq \Sigma$ be such that, for each $a \in \Sigma\setminus\Gamma$, $b \in \Gamma$ and $q \in Q$,
 we have $\delta(q, ab) = \delta(q, ba)$.


 Then, $\pi_{\Gamma}(L)$ is recognizable by a DFA
 with at most $|Q|$ states.
\end{lemma}
\begin{proof}
 Intuitively, we take the input automaton and leave out all unobservable transitions
 and make a state accepting if, in the input automaton, we can go from this state
 to a final state by a word formed out of the deleted letters.
 
 
 Let $\mathcal B = (Q, \Gamma, \delta_{|\Gamma}, q_0, E)$
 be the DFA with $\delta_{|\Gamma}(q, x) = \delta(q,x)$,
 the same start state $q_0$
 and $E = \{ p \in Q \mid \exists q \in F \ \exists u \in (\Sigma \setminus \Gamma)^* : \delta(p, u) = q \}$.
 Then, $L(\mathcal B) = \pi_{\Gamma}(L(\mathcal A))$.
 
 
 If $\delta_{|\Gamma}(q_0, u) \in E$,
 then there exists $v \in (\Sigma\setminus\Gamma)^*$
 such that $\delta(q_0, uv) \in F$. So, $uv \in L(\mathcal A)$
 and $u = \pi_{\Gamma}(uv)$.
 
 
 Conversely, suppose $u = \pi_{\Gamma}(v)$ for some $v \in L(\mathcal A)$.
 By assumption, as we can successively push all letters in $\Sigma\setminus \Gamma$
 to the end, we have $\delta(q_0, v) = \delta(q_0, \pi_{\Gamma}(v)\pi_{\Sigma\setminus\Gamma}(v))$.
 So, $\delta(q_0, \pi_{\Gamma}(v)\pi_{\Sigma\setminus\Gamma}(v)) \in F$,
 which yields  $\delta_{|\Gamma}(q_0, \pi_{\Gamma}(v)) \in E$,
 hence $u \in L(\mathcal B)$.~\qed
\end{proof}

So, with Lemma~\ref{lem:centralizer}, we get the next result.

\begin{theoremrep}
\label{thm:proj_comm_lang}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a DFA
 such that $L(\mathcal A)$ is commutative.

 If $\Gamma \subseteq \Sigma$, then $\pi_{\Gamma}(L(\mathcal A))$
 is recognizable by a DFA with at most $|Q|$
 states.
\end{theoremrep}
\begin{proof} 
 First, note that, for each $q \in Q$, $a,b \in \Sigma$ and $u \in \Sigma^*$, we have
 \[
  \delta(q, abu) \in F \Leftrightarrow \delta(q, bau) \in F.
 \]
 Hence, those states are equivalent~\cite{HopUll79} 
 and if $\delta(q, ab) \ne \delta(q, ba)$, we can merge the states
 by identifying them and retaining only the transitions of one state,
 which still gives a recognizing automaton for $L(\mathcal A)$.
 
 Then, apply Lemma~\ref{lem:centralizer}.~\qed
\end{proof}









 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



\begin{comment}

\begin{corollary}
\label{cor:SCC_commutes}
 If $\Gamma \in \Sigma$ and $\Delta = \Sigma \setminus \Gamma$,

 then the $\Gamma$-orbits partition the state set.
 In particular, $\mathcal A$ is a state-partition automaton
 for the projection $\pi_{\Gamma} : \Sigma^* \to \Gamma^*$.
 %

\end{corollary}
\end{comment}


\begin{comment} 
Using the previous lemma, we can characterize those projections
involving commuting letters that yield state-partition automata.

\begin{theorem}
\label{thm:char_com_state_partition}
 Let $\Gamma \subseteq \Sigma$, $\Delta = \Sigma \setminus \Gamma$
 and $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a DFA.
 Suppose, for each $a \in \Gamma$, 
 $b \in \Delta$ and $q \in Q$ we have $\delta(q, ab) = \delta(q, ba)$.
 Then, $\mathcal A$ is a state-partition automaton for $\pi_{\Gamma}$ if and only
 if every $\Delta$-orbit reachable from $\operatorname{Orb}_{\Delta}(\{q_0\})$ in $\mathcal R_{\mathcal A}^{\Gamma}$
 is strongly connected in $\mathcal A_{|\Delta}$. 
\end{theorem}
\begin{proof}
 Recall that $\Delta$-orbits are stable for $\Delta$
 by definition.
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$.
 First, suppose the $\Delta$-orbits form strongly connected components in $\mathcal A_{|\Delta}$.
 Then, by Lemma~\ref{lem:SCC_commutes}, the letters in $\Gamma$
 permute these orbits and we find that the orbits reachable
 from the start orbit in the projection automaton form a partition\todo{in def state parittion, parition von erreichbaren zuständen. kleine abweichung von def in anderen papern. sprechweise reachable state.}
 of the reachable states in $\mathcal A$.
 
 
 Now, suppose some $\Delta$-orbit $\operatorname{Orb}_{\Delta}(q)$
 reachable from $\operatorname{Orb}_{\Delta}(\{q_0\})$ in $\mathcal R_{\mathcal A}^{\Gamma}$
 is not strongly connected in $\mathcal A_{|\Delta}$.
 Then, there exist $s, t \in \operatorname{Orb}_{\Delta}(q)$
 such that $t$ is reachable from $s$ in $\mathcal A_{|\Delta}$ 
 but not vice versa.
 But then, $\operatorname{Orb}_{\Delta}(t) \subsetneq \operatorname{Orb}_{\Delta}(s)$
 and the $\Delta$-orbits for states reachable from $q_0$
 do not form a partition of the reachable states.~\qed
\end{proof}
\end{comment}



\begin{comment}

We can use Lemma~\ref{lem:SCC_commutes} to deduce a sufficient condition
for a commutative automaton to be a state-partition automaton. We formulate this a little
bit more general in terms of commuting letters.

\begin{proposition}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a DFA
 and $\Sigma \subseteq \Sigma$ and $\Delta = \Sigma \setminus \Gamma$.
 Suppose, for each $a \in \Gamma$ and $b \in \Delta$
 we have $\delta(q, ab) = \delta(q, ba)$ for $q \in Q$.
 If every $\Delta$-orbit
 of the form\footnote{Note that if $\operatorname{Orb}_{\Delta}(\{q,q'\})$ is strongly connected,
 then $\operatorname{Orb}_{\Delta}(\{q,q'\}) = \operatorname{Orb}_{\Delta}(q) = \operatorname{Orb}_{\Delta}(q')$.}
 $\operatorname{Orb}_{\Delta}(q)$
 is strongly connected in $\mathcal A_{|\Delta}$, then $\mathcal A$ is a state-partition automaton 
 for the projection $\pi_{\Gamma}$.
\end{proposition}
\begin{proof} 
 Observe that $\Delta$-orbits are stable for $\Delta$
 by definition. 



 
 \begin{claiminproof}
  If
 
 
  %
 
  %
 
 \end{claiminproof}
 
 
 %

 
 
 
 Also, if the $\Delta$-orbits $\operatorname{Orb}_{\Delta}(q)$ for $q \in Q$
 are strongly connected in $\mathcal A_{\Delta}$.
 

 
 
 
 So, if they are also strongly connected, then, by Lemma~\ref{lem:SCC_commutes},
 and letter from $\Gamma$ permutes the $\Delta$-orbits.
 In particular, for $x \in \Gamma$, we find
 \[ 
  \mu(\operatorname{Orb}_{\Delta}(R), x) = 
 \]
 
 
 
\end{proof}
\end{comment}

The definition of normality could be seen
as a generalization of commutativity.
Hence, with Theorem~\ref{thm:orbits-normal-subgroup},
we can deduce the next statement.


\begin{proposition}
\label{cor:perm_com_are_state_partition}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$
 be a commutative permutation automaton and $\Gamma \subseteq \Sigma$.
 Then, $\mathcal A$ is a state-partition automaton for $\pi_{\Gamma}$.
\end{proposition}

However, there exist commutative automata that are not state-partition automata,
as shown by Example~\ref{ex:comm_proj_non_state_partition}.

\begin{example}
\label{ex:comm_proj_non_state_partition}
 Let $\mathcal A = (\{q_{\varepsilon}, q_a, q_b\}, \{a,b\}, \delta, q_{\varepsilon}, \{q_{\varepsilon}, q_b\})$
 with  
 \[
  \delta(q_x, y)  = \left\{ \begin{array}{ll}
   q_a & \mbox{if } x = \varepsilon, y = a; \\
   q_b & \mbox{if } x = \varepsilon, y = b; \\ 
   q_b & \mbox{if } x = a, y = b; \\
   q_x & \mbox{otherwise.}
   \end{array}
  \right.
 \]
 Then, $L(\mathcal A) = \{ u \in \{a,b\}^* \mid |u|_a = 0 \mbox{ or } |u|_b > 0 \}$.
 However, we see that $\operatorname{Orb}_{\{b\}}(q_{\varepsilon}) = \{ q_{\varepsilon}, q_b \}$,
 $\operatorname{Orb}_{\{b\}}(q_b) = \{q_b\}$
 and $\operatorname{Orb}_{\{b\}}(q_a) = \{q_a, q_b\}$. Hence,
 $\mathcal A$ is not a state-partition automaton for the projection 
 $\pi_{\{a\}} : \{a,b\}^* \to \{a\}^*$. Also,
 it is not a state-partition automaton for the projection
 onto $\{b\}^*$.
\end{example}


The proofs of Lemma~\ref{lem:centralizer} and Theorem~\ref{thm:proj_comm_lang}
also show that the projected language of a commutative permutation automaton
is recognizable by a permutation automaton, i.e., a group language.
On the other hand, in the general case, Example~\ref{ex:proj_perm_aut}
below gives a permutation automaton whose projected language is not a group language.
Also, most properties defined in terms of automata are preserved by projection
in the commutative case. For example the property of being aperiodic~\cite{Eilenberg1976,Pin86,DBLP:reference/hfl/Pin97}.
We give a more general statement next, showing that many classes from the literature~\cite{Eilenberg1976,Pin86,DBLP:reference/hfl/Pin97}
are closed under projection when restricted to commutative languages.


\begin{theoremrep}
 Let $\Sigma$ be an alphabet and $\Gamma \subseteq \Sigma$.
 Suppose $\mathcal V$ is a variety of commutative languages. If $L \in \mathcal V(\Sigma^*)$, then $\pi_{\Gamma}(L) \in \mathcal V(\Gamma^*)$.
 In particular, the variety of commutative languages is closed under projection.
\end{theoremrep}
\begin{proof}
 For varieties, the transformation monoid of the minimal complete automaton of a language $L \in \mathcal V(\Sigma^*)$
 is an element of the corresponding variety of monoids~\cite{Eilenberg1976,Pin86}.
 Let $\mathcal A$ be the minimal complete automaton of $L$.



 Then, we see that applying the construction
 of Lemma~\ref{lem:centralizer} also gives a complete automaton $\mathcal B$.
 The transformation monoid $\mathcal T_{\mathcal B}$
 is a submonoid of $\mathcal T_{\mathcal A}$
 by interpreting any $\delta_u \in \mathcal T_{\mathcal B}$, $u \in \Gamma^*$,
 as an element $\delta_u \in \mathcal T_{\mathcal A}$ with $u \in \Sigma^*$.
 By standard constructions~\cite{Eilenberg1976,Pin86},
 a transformation monoid recognizes a language if and only if the
 corresponding automaton recognizes the language.
 Hence, by Theorem~\ref{thm:proj_comm_lang},
 the transformation monoid recognizes $\pi_{\Gamma}(L)$.
 As varieties of monoids are closed under submonoids~\cite{Eilenberg1976,Pin86}, 
 we have $\mathcal T_{\mathcal B} \in \mathcal V$
 and so $\pi_{\Gamma}(L) \in \mathcal V(\Gamma^*)$.~\qed
\end{proof}

Hence, for example commutative locally-testable, piecewise-testable, star-free or group
languages are preserved under every projection operator, as these classes
form varieties~\cite{Pin86}.



\begin{remark}
 In~\cite{DBLP:journals/tcs/JiraskovaM12} it was stated that 
 languages satisfying the observer property, i.e.,
 that are given by a state-partition automaton for a given projection operator, 
 and the finite languages projected onto unary finite languages
 were the only known languages for which we can recognize the projected language
 with at most the number of states as the original language.
 Note that Theorem~\ref{thm:proj_comm_lang}
 provides genuinely new instances for which this holds true,
 see Example~\ref{ex:comm_proj_non_state_partition}.


\end{remark}

\begin{example}
\label{ex:proj_perm_aut}
Also, for projections, consider the group language given by the permutation
automaton
$\mathcal A = (\{a,b\}, \{0,1,2\}, \delta, 0, \{2\})$
with $a = (0,1)$ and $b = (0,1,2)$.
Then, $\pi_{\{b\}}(L(\mathcal A)) = bb^*$, which is not a group language. 
For example, $b$ is the projection of $ab \in L(\mathcal A)$,
or $bbb$ the projection of $abbab \in L(\mathcal A)$.
\end{example}








\subsection{A General State Complexity Bound}

Here, we state a tight upper bound
for the number of states of the projection
of a language recognized by a permutation automaton.

Our bound is parameterized by the number of states of the input
automaton and by the number of non-loop unobservable
transitions. More specifically, we consider the number of states that are incident
with non-loop unobservable transitions. Hence, we
disregard unobservable multi-transitions and do not take the direction into account, i.e., counting
multiple transitions resulting from multiple letters
between the same states only once and do not take their direction into account.
This is the same usage of this parameter as  in~\cite{DBLP:conf/ifipTCS/JiraskovaM12} for the general
case.



\begin{theorem}
\label{thm:upper_bound}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$
 be a permutation DFA and $\Gamma \subseteq \Sigma$.
 Set 
 $
  m = |\{\ p, q \in Q \mid p \ne q \mbox{ and } q \in \delta(p, \Sigma \setminus \Gamma) \}|.
 $

 Then, if $m > 0$, the projected language $\pi_{\Gamma}(L(\mathcal A))$
 is recognizable by a DFA
 with at most $2^{\mathstrut{|Q| - \lceil \frac{m}{2} \rceil}} - 1$
 states and if $m = 0$, the projected language is recognizable 
 by a DFA with at most $|Q|$ states.
\end{theorem}
\begin{proof}


 %

 %

 Set $\Delta = \Sigma \setminus \Gamma$,
 $S = \{ p, q \in Q \mid p \ne q \mbox{ and } q \in \delta(p, \Delta) \}$ and $T = \{ p \in Q \mid \forall x \in \Delta : \delta(p, x) = p \}$.
 Then, as $\mathcal A$ is a permutation automaton,
 $Q$ is the disjoint union of $S$ and $T$ and
 \begin{equation}
 \label{eqn:S_and_T}
  q \in T \Leftrightarrow \operatorname{Orb}_{\Delta}(q) = \{q\} \mbox{ and }
  q \in S \Leftrightarrow |\operatorname{Orb}_{\Delta}(q)| \ge 2.
 \end{equation}

 Set $\mathcal B = \mathcal R_{\mathcal A}^{\Gamma}$.
 If $m = 0$, then $Q = T$ and every $a \in \Delta$ 
 induces a self-loop at every state.
 In this case, it is clear that we can simply leave out all the transitions
 labeled with letters from $\Delta$
 and the resulting permutation automaton recognizes $\pi_{\Gamma}(L(\mathcal A))$.
 More formally, in the definition of $\mathcal B$, in this case,
 the starting state is $\{q_0\}$
 and as $\mathcal A$ is deterministic we have $|\delta(R, x)| \le |R|$
 for every $R \subseteq Q$. So, as the empty set is never reachable for permutation DFAs,
 only the singleton sets $\{q\}$
 are reachable in $\mathcal B$.
 
 Now, suppose $m = |S| > 0$, which implies $m \ge 2$.
 
 \begin{claiminproof}
  Let $m > 0$. Then, in $\mathcal B$ at most  $2^{|Q| - \lceil \frac{m}{2} \rceil} - 1$
  states are reachable from the start state.
 \end{claiminproof}
 \begin{claimproof}
  With the assumption $m > 0$, there exists $q \in Q$
  such that $|\operatorname{Orb}_{\Delta}(q)| > 1$.
  By Equation~\eqref{eqn:S_and_T} and Lemma~\ref{lem:orbits-partition},
  we have at most $|T| + \Big\lfloor \frac{|S|}{2} \Big\rfloor$
  many $\Delta$-orbits, where the maximum number of $\Delta$-orbits is reached if
  every $\Delta$-orbit of a state from $S$ has size exactly two if $|S|$
  is even or every such orbit has size two, except one
  that has size three, if $|S|$ is odd.
  By Lemma~\ref{lem:orbits-partition},
  the sets $\operatorname{Orb}_{\Delta}(\{q\})$, $q \in Q$,
  partition the state set and, for every $R \subseteq Q$,
  we have $\bigcup_{q \in R} \operatorname{Orb}_a(q) = \operatorname{Orb}_a(R)$.
  So, by Equation~\eqref{eqn:def_mu}, every set
  reachable is a union of $\Delta$-orbits,
  i.e., every such set corresponds uniquely 
  to a subset of $\Delta$-orbits for a single state.
  Finally, note that, as $\mathcal A$ is a permutation automaton,
  and hence complete, we have $\delta(R, x) \ne \emptyset$
  for every non-empty $R \subseteq Q$, which also gives that in $\mathcal B$
  the empty set is not reachable.
  So, in total, we find that at most 
  \[ 2^{|T| + \Big\lfloor \frac{|S|}{2} \Big\rfloor} - 1
   = 2^{|Q| - m + \lfloor \frac{m}{2} \rfloor} - 1
   = 2^{|Q| - \lceil \frac{m}{2} \rceil} - 1
  \]
  subsets of states are reachable.
 \end{claimproof}
 
  


 
 So, we have shown the upper bound.~\qed 
\end{proof}


\begin{comment}
\begin{theorem}
 There exists a permutation automaton $\mathcal A = (\Sigma, Q, \delta, q_0, F)$
  and $\Gamma \subseteq \Sigma$
  with $|\Gamma| = 4$, $|\Sigma| = 5$
  and one unobservable transition such that
  the minimal automaton for $\pi_{\Gamma}(L)$
  needs $2^{n - 1} - 1$ states.
\end{theorem}
\begin{proof}
   Let $Q = \{1,\ldots, n\}$ and $\Sigma = \{a,b,c,d,e\}$ with 
   \begin{align*
    \delta(1, a) & = 2, \delta(2, a) = 1; \\
    \delta(2, b) & = 3, \delta(3, b) = 2; \\
    \delta(1, c) & = 3, \delta(3, c) = 1, \delta(2, c) = 4, \delta(4,c) = 2; \\
    \delta(3, d) & = 4, \delta(4, d) = 3; \\
    \delta(3, e) & = 4, \delta(4, e) = 5, \ldots, \delta(n-1,e) = n, \delta(n, e) = 3.
   \end{align*}
  Let $s_0 = 3$ be the start state and $F = \{ 3 \}$
  be the final state. Set $\Gamma = \{b,c,d,e\}$ and $\Delta = \{a\}$.  We will show that in $\mathcal B$
  all nonempty states $A \subseteq Q$ 
  with $\{1,2\} \subseteq A$ or $\{1,2\} \cap A = \emptyset$
  are reachable and distinguishable, i.e., those states
  of the form $\operatorname{Orb}_{\Delta}(B)$ for $B \subseteq Q$,
  and we have $2^{|Q| - 1} - 1$ such states. 
 
 
  \begin{claiminproof}
   All nonempty subsets $A \subseteq Q$
   with $\{1,2\}\cap A = \emptyset$ or $\{1,2\} \subseteq A$
   are reachable in $\mathcal B$.
  \end{claiminproof}
  \begin{claimproof}
  
  
  
  
  
  
   We show inductively that for each $1 \le k \le n$,
   every subset $B \subseteq Q$ with $|B| = k$
   and $\{1,2\} \subseteq B$ or $\{1,2\} \cap B = \emptyset$
   is reachable.
   
  
   
   \begin{enumerate}
   \item The base case $k = 1$ corresponds to the statement
       that the sets $\{q\}$, $q \in \{3,\ldots, n\}$ are reachable.
       Let $\operatorname{Orb}_{\Delta}(A) = \{q\}$, then $A = \{q\}$ with $q \in \{3,\ldots, n\}$
       and there exists $u \in \{d, e\}^*$
       such that $\delta(q_0, u) = q$
       and as $\delta(1, d) = \delta(1, e) = 1$, this yields $\mu(\operatorname{Orb}_{\Delta}(\{p\}), u) = \operatorname{Orb}_{\Delta}(\{q\}) = \{q\}$.
       
       
   \item Suppose $1 \le k < n$. Let $C \subseteq \{3,\ldots, n\}$
     with $|C| = k$. By assumption, $C$ is reachable in $\mathcal B$.
   Then there exists $w \in \{b,e\}^*$
   such that $2 \in \delta(C, w)$.
   So, $\{1,2\} \subseteq \operatorname{Orb}_{\Delta}(\delta(C, w)) = \mu(C, w)$
   and $|\mu(C, u)| = |C| + 1$.
   Hence, we have reached at least one subset $A = \mu(B, w)$
   with $|A| = k + 1$
   such that $\{1,2\} \subseteq A$. Next, we show that we can reach every other
   subset $B \subseteq Q$ with $|B| = k + 1$ and $\{1,2\}\subseteq B$
   or $\{1,2\} \subseteq B$.
   If $B \subseteq Q$ with $\{1,2\} \subseteq B$,
   then let $u \in \{d,e\}^*$ with $\delta(A, u) = B$,
   then $\mu(\operatorname{Orb}_{\Delta}(A), u) = \operatorname{Orb}_{\Delta}(B) = B$.
   If $B \subseteq Q$ with $\{1,2\} \cap B = \emptyset$,
   then let $u \in \{d,e\}^*$
   with $\{3,4\} \cap \delta(A, u) = \emptyset$.
   Then, $\{1,2\} \cap \delta(A, uc) = \emptyset$.
   Choose $v \in \{d,e\}^*$
   with $\delta(A, ucv) = B$.
   In this case, $\mu(\operatorname{Orb}_{\Delta}(A), ucv) = \operatorname{Orb}_{\Delta}(B) = B$.
   \end{enumerate}
   So, by induction, the claim holds true.
  \end{claimproof}
  
  \begin{claiminproof}
   All nonempty subsets $A \subseteq Q$ with $\{1,2\} \cap A = \emptyset$
   or $\{1,2\} \subseteq A$ are distinguishable in $\mathcal B$.
  \end{claiminproof}
  \begin{claimproof}
  Let $A, B \subseteq Q \setminus \{1\}$ be distinct and nonempty
  and $F = \{q_f\}$.
  Without loss of generality, suppose $q \in A \setminus B$.
  Choose $u \in \{b,e\}^*$ such that $\delta(q, u) = q_f$.
  Then, as $\delta(1, b) = \delta(1, e) = 1$, we have\footnote{More generally,
  we can show that for every $A, B \subseteq Q$
  we have $\delta(A, u) = B$
  iff $\mu(\operatorname{Orb}_{\Delta}(A), u)) = \operatorname{Orb}_{\Delta}(B)$.}
  \[
   q_f \in \mu(\operatorname{Orb}_{\Delta}(A), u)
  \]
  and $q_f \notin \mu(\operatorname{Orb}_{\Delta}(B), u)$.
  \end{claimproof}
  This shows that $\mathcal B$ is minimal and it has $2^{|Q| - 1} - 1$
  states.~\qed
\end{proof}
\end{comment}

\begin{toappendix}
For the lower bound, we need the following well-known fact from permutation group theory~\cite{Isaacs95}.

\begin{lemma}\label{lem:transposition_and_cycle_gen_Sn}
 Let $\sigma, \tau : \{1,2,\ldots, n\} \to \{1,2,\ldots,n\}$ for $n \ge 2$
 be the permutations $\sigma = (1,\ldots,n)$
 and $\pi = (1,2)$.
 Then, every permutation of $\{1,2,\ldots,n\}$ could be written as a product
 of the permutations~$\sigma$ and~$\tau$.
\end{lemma}
\end{toappendix}

Next, we show that the bound stated in the previous theorem
is actually tight for permutation automata.


 \input{tikz_lower_bound}
 
\begin{theoremrep}
\label{thm:lower_bound}
 Let $n, m > 0$ be such that $0 < 2m + 1 < n$, $\Sigma = \{a,b,c,d,e,f,g\}$
 and $\Gamma = \{b,c,d,e,f,g\}$.
 Then, there exists a permutation automaton $\mathcal A = (Q, \Sigma, \delta, q_0, F)$
 with $2m$
 states incident to non-loop unobservable transitions for~$\pi_{\Gamma}$, i.e.,
 \[
  2m = |\{\ p, q \in Q \mid p \ne q \mbox{ and } q \in \delta(p, \Sigma \setminus \Gamma) \}|,
 \]
 such that every DFA for $\pi_{\Gamma}(L(\mathcal A))$
 needs at least $2^{n - m} - 1$ 
 states.
\end{theoremrep}
\begin{proofsketch}
 See Figure~\ref{fig:lower_bound} for a permutation automaton
 giving the lower bound.
 The automaton has $n$ states, and the letters act the following way:
 \[ 
 \begin{array}{llll}
     a & = (1,2)(3,4) \cdots (2m-1, 2m), \\ 
     b & = (2m + 1, 2m + 2), & c = (2m + 1, 2m + 2, \ldots, n), \\
     d & = (1,3)(2,4), & e = (1,3,\ldots,2m-1)(2,4,\ldots, 2m), \\
     f & = (1,n), & g = (1,n)(2, n-1).
 \end{array}
 \]
 With $\Delta = \{a\}$, the $\Delta$-orbits are 
 $\{1,2\},\{3,4\},\ldots, \{2m-1,2m\}, \{2m+1\}, \ldots, \{n\}$.
 The letters $b,c$ are chosen such that every permutation of the 
 states $\{2m+1,\ldots,n\}$ could be written as a word over them,
 and the letters $d$ and $e$ such that every permutation on the
 $\Delta$-orbits $\{1,2\}, \ldots, \{2m-1,2m\}$ could be written
 as a word over them. The letters $f$ and $g$ help to map between
 these $\Delta$-orbits in such a way that every non-empty
 union of $\Delta$-orbits is reachable, and all these $\Delta$-orbits
 give distinguishable states. By mapping onto the two element $\Delta$-orbits
 and back, we can enlarge the sets that are reachable.\qed
 
 
\end{proofsketch}
\begin{proof}
 Let $\Sigma = \{a,b,c,d,e,f,g\}$ and $\mathcal A = (\Sigma, Q, \delta, q_0, F)$
 with $Q = \{1,2,\ldots, n\}$,
 start state $q_0 = n$ and $F = \{ n \}$. 
 The transitions were already defined in the proof sketch
 in the main text. So, here we only give
 the proof in detail.
 Note that, the letters $d$ and $e$
 permute the subsets $\{ i, i + 1\}$
 for $i \in \{1,\ldots, 2m\}$ and we
 have, for each $i, j \in \{1,3,\ldots, 2m-1\}$, 
 that there exists, by Lemma~\ref{lem:transposition_and_cycle_gen_Sn}
 and the definition of the transition function in the projection automaton,
 a word $u \in \{d,e\}^*$
 such that 
 \[
  \mu(\{ i, i + 1 \}, u) = \{ j, j + 1 \}.
 \]
 Also, observe that for $u \in \{b,c\}^*$ and $v \in \{d,e\}^*$
 we have $\delta(q, uv) = \delta(q, vu)$ for each $q \in Q$.
 
 
 Set $\Delta = \{a\}$ and $\Gamma = \{b,c,d,e,f,g\}$. We will refer to the projection automaton
 \[
  \mathcal R_{\mathcal A}^{\Gamma} = (\mathcal P(Q), \Gamma, \mu, \operatorname{Orb}_{\Delta}(q_0), E) 
 \]
 in the following. Here, we have $\operatorname{Orb}_{\Delta}(q_0) = \{q_0\}$.
 
 
 
 
 
 Let $S$
 be the set
 \begin{multline*}
     \{ \emptyset \ne A \subseteq Q \mid 
     \forall i \in \{1,3,\ldots, 2m - 1\} : \{ i, i + 1 \} \subseteq A \mbox{ or } \{ i, i + 1 \} \cap A = \emptyset \}.
 \end{multline*}
 Then, $S = \{ \operatorname{Orb}_{\Delta}(A) \mid \emptyset \ne A \subseteq Q \}$
 and $S$ could be seen as a subset of states for the projection 
 automaton $\mathcal R_{\mathcal A}^{\Gamma}$.
 
  

 The following equations are readily implied and will be used frequently without further mention:
 \begin{align}
     \delta(A, u)  & = \mu(A, u) \mbox{ for } A \in S, u \in \{d,e\}^* \mbox{ or } u \in \{b,c\}^*; \label{eqn:b_c_d_e_permute_a_orbits} \\
     \mu(\{n\}, x) & = \{1,2\} \mbox{ for } x \in \{f,g\}; \label{eqn:g_and_n}\\ 
     \mu(\{1,2\}, f) & = \{1,2\} \cup \{n\}; \\ 
     \mu(A \cup B, u) & = \mu(A, u) \cup \mu(B, u) \mbox{ for } A, B \subseteq Q, u \in \Gamma^*.
 \end{align}
 The last one also implies, for $A \subseteq B$,
 that $\mu(A, u) \subseteq \mu(B, u)$ for $u \in \Gamma^*$.
   
  
  
 We will also use the following function $h : \{1,\ldots, n\} \to \{1,\ldots, n - m \}$
 given by $h(i) = h(i+1) = \frac{i+1}{2}$ for $i \in \{1,3,\ldots, 2m - 1 \}$
 and $h(i) = i - m$ for $i \in \{ 2m + 1, \ldots,n\}$
 in the following arguments.
  
  
 \begin{claiminproof}
  We have $|S| = 2^{n - m} - 1$. 
 \end{claiminproof}
 \begin{claimproof}
  We have $S = \{ h^{-1}(A) \mid \emptyset \ne A \subseteq \{1,\ldots, n - m\} \}$
  and $h^{-1}(A) \ne h^{-1}(B)$ for distinct $A, B \subseteq \{1,\ldots, n -m \}$.
  So, as there exist $2^{n - m} - 1$ non-empty subsets
  of $\{1,\ldots, n - m\}$, the claim follows.
 \end{claimproof}
 
 \begin{claiminproof}
  The subsets in $S$ are all reachable as states of $\mathcal R_{\mathcal A}^{\Gamma}$.
 \end{claiminproof}
 \begin{claimproof}
  If $A \in S$, then there exists a non-empty set $B \subseteq \{1,\ldots,n-m\}$
  such that $A = h^{-1}(B)$.
  We do induction on the size of $B$.
  
  \begin{enumerate}
  \item Suppose $|B| = 1$. 
   First, if $h^{-1}(B) \subseteq \{2m+1,\ldots,n\}$,
   then $|h^{-1}(B)| = 1$.
   There exists a permutation of $\{2m+1,\ldots,n\}$
   that maps $q_0$ to the state in $h^{-1}(B)$
   Then, by Lemma~\ref{lem:transposition_and_cycle_gen_Sn},
   there exists $u \in \{b,c\}^*$
   such that $\delta(q_0, u) \in h^{-1}(B)$.
   As the letters $b$ and $c$
   permute the $\Delta$-orbits, see also Equation~\eqref{eqn:b_c_d_e_permute_a_orbits}, 
   and do not map anything in $\{2m+1,\ldots,n\}$
   to a state outside of this set,
   we have, for every prefix\footnote{The word $v$ is a prefix of $u$, if there exists $w \in \Sigma^*$ such that $u = vw$.} $v$ of $u$,
   \[
   \mu(\{q_0\}, v) = \operatorname{Orb}_{\Delta}(\delta(\{ q_0 \}, v) = \{ \delta(q_0, v) \} 
   \] 
   and so $\mu(\{q_0\}, u) = \{ \delta(q_0, u) \} = h^{-1}(B)$.
  
   Otherwise, suppose $h^{-1}(B) = \{ i, i + 1 \}$
   for $i \in \{1,3,\ldots, 2m-1\}$.
   We have
   \[
    \mu(\{q_0\}, f) = \operatorname{Orb}_{\Delta}(\delta(\{q_0\}, f)) = \{1,2\}. 
   \]
   By Lemma~\ref{lem:transposition_and_cycle_gen_Sn},
   there exists a word $u \in \{d,e\}^*$ such that
   $\delta(\{1,2\}, u) = \{i,i+1\}$
   and as the letters $d$ and $e$
   permute the $\Delta$-orbits, see also Equation~\eqref{eqn:b_c_d_e_permute_a_orbits}, 
   and do not map anything in $\{1,\ldots,2m\}$
   to a state outside of this set,
   we find $\mu(\{1,2\}, u) = \{i, i + 1\}$
   and so $\mu(\{q_0\}, fu) = h^{-1}(B)$.
   
   \medskip 
   
  \item Suppose $|B| > 1$.
   Let $k \in B$ and consider $C = B \setminus \{k\}$.
   Inductively, there exists $u \in \Gamma^*$
   such that $\mu(\{q_0\}, u) = h^{-1}(C)$. So, we only need to show that we could reach $h^{-1}(B)$
   from $h^{-1}(C)$.
   We distinguish several cases.
   
   \begin{enumerate}
   \item Suppose $|h^{-1}(k)| = 2$ and $h^{-1}(C) \cap \{2m+1, \ldots, n\}\ne \emptyset$.   
    
    \medskip
    
    Let $v \in \{b,c\}^*$
    describe the permutation that interchanges $n$
    with some state in $h^{-1}(C)$
    (or the identity transformation if $n \in h^{-1}(C)$) and maps everything else to itself
    and, similarly, $w \in \{d,e\}^*$ the permutation
    that interchanges $h^{-1}(k)$ with $\{1,2\}$ (or the identity transformation if $h^{-1}(k) = \{1,2\}$)
    and maps everything else (also the other $\Delta$-orbits)
    to itself. Note that $\delta_{vv}$ and $\delta_{ww}$ 
    represent the identity transformation.
    Existence of these words is guaranteed by Lemma~\ref{lem:transposition_and_cycle_gen_Sn}.
    Then,
    \begin{equation}\label{eqn:no_12_in_set}
     \{1,2\} \cap \mu(h^{-1}(C), w) = \emptyset.
    \end{equation}
    and 
    \[ 
     n \in \mu(h^{-1}(C), v). 
    \]
    Also, note that $\delta(n, v) \in h^{-1}(C)$, so $w$ acts like the identity transformation on $\{2m+1,\ldots,n\}$
    and $\{n\} \cap h^{-1}(C) \setminus\{\delta(n,v)\} = \emptyset$.
    Recall that the words $v$ and $u$ permute the $\Delta$-orbits,
    and so application of $\delta$ to $\Delta$-orbits and $\mu$ give the same result,
    see also Equation~\eqref{eqn:b_c_d_e_permute_a_orbits}.
    Using all this, we find 
   
    \begin{align*} 
    &  \mu(h^{-1}(C), vwffvw) \\
     & = \mu(\mu(h^{-1}(C), v), wffvw) \\ 
      & = \mu(\{n\} \cup \mu(h^{-1}(C) \setminus \{\delta(n,v)\}, wffvw) \\
      & =\mu(\{n\}, wffvw) \cup \mu(h^{-1}(C) \setminus\{\delta(n,v)\}, wffvw) \\
        & = \mu(\{n\}, ffvw) \cup \mu(h^{-1}(C) \setminus\{\delta(n,v)\}, wvw) & \mbox{[Equation~\eqref{eqn:no_12_in_set}]} \\
       & = \mu(\{1,2\}, fvw) \cup \mu(h^{-1}(C) \setminus \{\delta(n,v)\}, wvw) \\
       & = \mu(\{1,2,n\}, vw) \cup \mu(h^{-1}(C)\setminus \{\delta(n,v)\}, wvw) \\
       & = \mu(\{1,2\},vw) \cup \{ \delta(n, vw) \} \cup \mu(h^{-1}(C) \setminus \{\delta(n,v)\}, wvw) \\
       & =\mu(\{1,2\},vw) \cup \{ \delta(n, vw) \} \cup \mu(h^{-1}(C) \setminus \{n\},vww) \\ 
       & = \mu(\{1,2\},vw) \cup \{ \delta(n, v) \} \cup \mu(h^{-1}(C) \setminus \{n\},ww) \\ 
       & = \mu(\{1,2\},vw) \cup \{ \delta(n, v) \} \cup \mu(h^{-1}(C) \setminus \{n\},ww) \\ 
       & = \mu(\{1,2\},w) \cup \{ \delta(n, v) \} \cup \mu(h^{-1}(C) \setminus \{n\},ww) \\
       & = \mu(\{1,2\},w) \cup \{ \delta(n, v) \} \cup \mu(h^{-1}(C) \setminus \{n\},ww) \\
        & = \mu(\{1,2\},w) \cup \{ \delta(n, v) \} \cup h^{-1}(C) \setminus \{n\} \\
       & = h^{-1}(k) \cup h^{-1}(C) \\
       & = h^{-1}(B).
    \end{align*}
    
     \item Suppose $|h^{-1}(k)| = 2$ and $h^{-1}(C) \cap \{1, \ldots, 2m\}\ne \emptyset$.   
    
    \medskip
    
     In that case, there exists some minimal $i \in \{1,3,\ldots, 2m-1\}$
     such that $\{i,i+1\} \subseteq h^{-1}(C)$.
     We only sketch the argument, as it is similar to the other cases, and give a more bird's eye view here. Existence
     of all the words is guaranteed by Lemma~\ref{lem:transposition_and_cycle_gen_Sn},
     and, as before, we choose some of the words such that $\delta$ and $\mu$
     coincide on the $\Delta$-orbits (but, of course, not on the final concatenation of all words, as
     we want to enlarge the sets).
     First, choose a word $v \in \{d,e\}^*$ that 
     interchanges $\{1,2\}$ and $\{i,i+1\}$ and maps every other $\Delta$-orbit
     of a single state to itself, or let $v$ be the identity transformation
     if $\{1,2\} = \{i,i+1\}$.
     Then, apply $v$ to $h^{-1}(C)$ and then apply $g$.
     The resulting set contains $\{n,n-1\}$.
     Then, apply~$f$. The result contains $\{1,2\}, \{n-1\}$ and all the previous 
     states. 
    
    
     Then, apply $v$ again. This, essentially, reverses all the previous operations 
     on the states in $\{1,\ldots,2m\}$. So, we get the state set $h^{-1}(C) \cup \{n-1\}$.
     Let $w \in \{d,e\}^*$ be a word that interchanges 
     $\{1,2\}$ with $h^{-1}(k)$ or the identity transformation if both are equal.
     Then, if we apply $w$ we end up with a set in $\{1,\ldots, 2m\}$ that does not contain $\{1,2\}$
     but $\{n-1\}$. Then, apply $g$
     and $\{n-1\}$ gets mapped to $\{1,2\}$ by $\mu$, and everything else remains the same.
     A final application of $w$ gives $h^{-1}(k) \cup h^{-1}(C)$.
    
     \medskip
    
    \item $|h^{-1}(k)| = 1$ and $h^{-1}(C) \cap \{2m+1,\ldots,n\} \ne \emptyset$.
    
     \medskip 
     
     By Lemma~\ref{lem:transposition_and_cycle_gen_Sn}
     there exist $v, w \in \{b,c\}^*$
     such that
     \begin{enumerate}
     \item $v$ represents the permutation that interchanges $n-1$
      with the state in $h^{-1}(k)$ or  the identity permutation
      if $h^{-1}(k) = \{n-1\}$,
     
     \item $w$ represents the permutation that interchanges $n$
      with some state in $\delta(h^{-1}(C) \cap \{2m+1,\ldots,n\}, v) \subseteq \{2m+1,\ldots,n\}$
      or the identity permutation if $n \in \delta(h^{-1}(C) \cap \{2m+1,\ldots,n\}, v)$.
     \end{enumerate}
     
     Then, also using $h^{-1}(k) \subseteq \{ 2m+1, \ldots,n \} \setminus h^{-1}(C)$
     and Equation~\eqref{eqn:b_c_d_e_permute_a_orbits},
     we have $n - 1 \notin \mu(h^{-1}(C), v)$
     in both cases $n - 1 \in h^{-1}(C)$, when the state in $h^{-1}(k)$
     gets mapped to $n - 1$, or $n - 1\notin h^{-1}(C)$,
     as then the states $\{ h^{-1}(k), n - 1\}$ outside of $h^{-1}(C)$
     are swapped (or mapped to itself if they are equal) and everything else is mapped to itself.
     Furthermore,
     \[
     n - 1 \notin \mu(h^{-1}(C), vw)
     \] 
     as $n - 1 \notin \mu(h^{-1}(C), v)$
     implies that $w$ interchanges $n$ with some state different
     from $n - 1$ or is the identity permutation.
     Also, by choice of $w$,
     \[
       n  \in  \mu(h^{-1}(C), vw).
     \]
     So, by Equation~\eqref{eqn:g_and_n},
     \[
      \{1,2\} \subseteq \mu(h^{-1}(C), vwg) 
     \]
     and hence
     \[
      \{n-1,n\} \subseteq \mu(h^{-1}(C), vwgg). 
     \]
     As $g$ only moves $\{1,2,n-1,n\}$ by swapping $1$ with $n$ and $2$ with $n-1$,
     and by the choice of $w$, we have
     \[
      \mu(h^{-1}(C), vwggw) = \mu(h^{-1}(C), v) \cup \mu(\{n-1\}, w).
     \]
     As written above, because of $n - 1 \notin \mu(h^{-1}(C), v)$,
     we have $\delta(n-1, w) = n -1$ and so, by Equation~\eqref{eqn:b_c_d_e_permute_a_orbits}, 
     the above equals
     \[
      \mu(h^{-1}(C), v) \cup \{n-1\}.
     \]
     By choice of $v$ and Equation~\eqref{eqn:b_c_d_e_permute_a_orbits}, 
     $\mu(h^{-1}(C), vv) = h^{-1}(C)$ 
     and $\mu(\{n-1\}, v) = h^{-1}(k)$.
     So,
     \[
      \mu(h^{-1}(C), vwggwv) = h^{-1}(C) \cup h^{-1}(k) = h^{-1}(B).
     \]
     
    \item $|h^{-1}(k)| = 1$ and $h^{-1}(C) \cap \{2m+1,\ldots,n\} = \emptyset$.   
      
      \medskip 
      
      Then, as $C \ne \emptyset$,
      there exists $i \in \{1,\ldots, 2m\}$
      such that $\{i,i+1\} \subseteq h^{-1}(C)$.
      Let $v \in \{d,e\}^*$ be the permutation that
      interchanges $\{i, i +1\}$ with $\{1,2\}$
      or the identity transformation if $\{i,i+1\} = \{1,2\}$.
      Also, let $w \in \{b,c\}^*$ be a
      permutation that maps $n$ to the state in $h^{-1}(k)$.
      Then,
      \[
       n \in \mu(h^{-1}(C), vf).
      \]
      Note that, after applying $vf$, as $2$ is not moved by $f$, the $\Delta$-orbit
      $\{1,2\}$ is still contained in $\mu(h^{-1}(C), vf)$.
      Then,
      \[
       \mu(h^{-1}(C), vfvw) = h^{-1}(C) \cup h^{-1}(k) = h^{-1}(B).
      \]
    \end{enumerate}
    
    
    
    
    
    
    


 
   So, we have shown that $h^{-1}(B)$ is reachable from $\{q_0\}$
   in $\mathcal R_{\mathcal A}^{\Gamma}$ in all cases for $h^{-1}(C)$.
  \end{enumerate}

   By induction, we can conclude that every set $h^{-1}(B) \in S$
   with $B \ne \emptyset$ is reachable in $\mathcal R_{\mathcal A}^{\Gamma}$.
 \end{claimproof}
 
 
 \begin{claiminproof}
  The subsets in $S$ are distinguishable as states of $\mathcal R_{\mathcal A}^{\Gamma}$.
 \end{claiminproof}
 \begin{claimproof}
  Let $A, B \in S$ be distinct.
  Without loss of generality, suppose $q \in A \setminus B$.
  We distinguish two cases.
  \begin{enumerate}
  
  \item Suppose $q \in \{2m+1,\ldots,n\}$. By\footnote{The letter $b$ interchanges $2m+1$
  and $2m+2$ and the letter $c$ cyclically permutes the states $\{2m+1,\ldots,n\}$.
  So, by Lemma~\ref{lem:transposition_and_cycle_gen_Sn},
  every permutation of the states $\{2m+1,\ldots,n\}$ could be written
  as a word over $b$ and $c$.}
  Lemma~\ref{lem:transposition_and_cycle_gen_Sn},
  there exists $u \in \{b,c\}^*$
  such that $\delta(q, u) \in F$.
  As $|F| = 1$ and $u$ is a permutation of all the states $Q$,
  for each $q' \in Q \setminus \{q\}$,
  we have $\delta(q', u) \notin F$.
  In particular, we find $\delta(B, u) \cap F = \emptyset$
  and $\delta(A, u) \cap F \ne \emptyset$.
  Then, note that for $q \in \{2m+1,\ldots,n\}$,
  and $u \in \{b,c\}^*$, as $\operatorname{Orb}_{\Delta}(q)$ is a singleton set
  and $\delta(\{2m+1, \ldots, n), b) = \delta(\{2m+1,\ldots,n\}, c) = \{2m+1,\ldots,n\}$,
  we find $\mu(A, u) = \delta(A, u)$
  and $\mu(B, u) = \delta(B, u)$. 
  Hence, $\mu(B, u) \cap F = \emptyset$
  and $\mu(A, u) \cap F \ne \emptyset$
  and $A$ and $B$ are distinguishable in $\mathcal R_{\mathcal A}^{\Gamma}$.
  \item Suppose $q \in \{1,\ldots,2m\}$. Then
   $\operatorname{Orb}_{\Delta}(q) \subseteq A$.
   By Lemma~\ref{lem:transposition_and_cycle_gen_Sn}, there
   exists $u \in \{d,e\}^*$
   such that $\delta(\operatorname{Orb}_{\Delta}(q), u) = \{1,2\}$.
   As the letters $d$ and $e$
   permute the $\Delta$-orbits, for every prefix
   $v$
   of $u$, we have
   \[
    \mu(\operatorname{Orb}_{\Delta}(q), v) = \operatorname{Orb}_{\Delta}(p)
   \]
   for some $p \in \{1,\ldots,2m\}$, i.e, the image is the $\Delta$-orbit of a single state,
   and so
   $\mu(\operatorname{Orb}_{\Delta}(q), u) = \{1,2\}$.
   Then,
   \[
    \mu(\{1,2\}, f) = \operatorname{Orb}_{\Delta}(\delta(\{1,2\}, f))
     = \operatorname{Orb}_{\Delta}(\{2,n\}) = \{1,2,n\}
   \]
   and so $\mu(A, uf) \cap F \ne \emptyset$.
   As $uf$ permutes the states $Q$,
   we have $\delta(B, uf) \cap F = \emptyset$.
   Also, as $u$ permutes the $\Delta$-orbits,
   \[
    \mu(\operatorname{Orb}_{\Delta}(q), u) \cap \{1,2\} = \emptyset.
   \]
   So $\mu(\operatorname{Orb}_{\Delta}(q), uf) \cap F = \emptyset$ (more specifically, here $\mu(\operatorname{Orb}_{\Delta}(q), uf) = \mu(\operatorname{Orb}_{\Delta}(q), u)$).
   \end{enumerate}
  Hence, in both cases the states $A$
  and $B$ are distinguishable in $\mathcal R_{\mathcal A}^{\Gamma}$.
 \end{claimproof}

 So, the states in $S$ of $\mathcal R_{\mathcal A}^{\Gamma}$
 are all reachable and distinguishable. 
 Also, the input automaton is initially connected,
 so, as written at the end of Remark~\ref{rem:minimal_aut},
 every state is coaccessible, and so, also as written in Remark~\ref{rem:minimal_aut},
 every state in $\mathcal R_{\mathcal A}^{\Gamma}$
 is coaccessible. Note that we needed every state to be coaccessible, as
 we are talking about minimal DFAs, which could be partial. For example, a reachable non-coaccessible
 non-final state might be distinguishable from every other state, but nevertheless could be left out.
 Hence, the minimal
 automaton needs at least $|S|$ states and the statement follows.~\qed
\end{proof}

\begin{remark}
 Note that if $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ is initially connected
 and
 has the property that from every state $q \in Q$ a final state
 is reachable, then also $\mathcal R_{\mathcal A}^{\Gamma}$
 has this property. As permutation DFAs are complete by definition,
 this implies that the tight bound stated in Theorem~\ref{thm:upper_bound}
 remains the same if we would additionally demand the resulting DFA for the projection
 to be complete. 
\end{remark}


We used an alphabet of size seven to match the bound. So, the question arises
if we can reach the bound using a smaller alphabet. I do not know the answer yet, but 
by using a result from~\cite[Theorem 6]{DBLP:journals/tcs/JiraskovaM12}
that every projection onto a unary language needs less than $\exp((1 + o(1))\sqrt{n \ln(n)})$
states, we can deduce that we need at least a ternary alphabet to reach the bound
stated in Theorem~\ref{thm:upper_bound}.
For the bound stated in Theorem~\ref{thm:upper_bound} is lowest possible, apart from the trivial
case $m = 0$, 
if $m = n$. Then, the bound is $2^{\lfloor n / 2 \rfloor} - 1$.
However, asymptotically, this grows way faster than $\exp((1 + o(1))\sqrt{n \ln(n)})$.
In fact, the ratio of both expressions could be arbitrarily large.

\begin{proposition}
 Each permutation automaton $\mathcal A$ such that $\pi_{\Gamma}(L(\mathcal A))$, for a non-empty and proper subalphabet $\Gamma \subseteq \Sigma$,
 attains the bound
 stated in Theorem~\ref{thm:upper_bound} with $m > 0$ must be over an alphabet with at least three letters
 and $|\Gamma| \ge 2$.
\end{proposition}



\section{State-Partition Automata and Normal Subgroups}
\label{sec:normal_subgroups}

\input{normal_subgrp}

\section{Shift}

$2^Q \times 2^{Q \times 2^Q}$
jedesmal, wenn $q \in F$ im vorderteil, $(q, {q_0})$ im hinterteil hinzufügen,
akzeptieren, wenn $q \in A$ für $(q, A)$ 
bei perm automat vorne immer $Q$

\section{The Up- and Downward Closure}


\begin{proposition}
 upward closure mit $n$
\end{proposition}
\begin{proof}
 Schleifen, d.h. in potenzmenge bleibt jedes menge drin, und man vergrößert sich um 
 mindestens eins, und falls nicht, dann permutiert dieser buchstabe.
\end{proof}


\begin{proposition}
 downward closure immer $Sigma^*$.
\end{proposition}
\begin{proof}
 beliebiges wort, bild wenn von startzustand, landet in beliebigen, dann was dranhängen, so dass final
 [also folgt, da jeder zustand co-reachable/co-accessible], sogar unter suffix und präfix ordnungen,
 also auch für diese ganzen ordnungen.
\end{proof}



\end{comment}


\section{Introduction}
\label{sec:introduction}

\input{introduction}




\input{preliminaries}


\section{Projection on Permutation Automata}


\input{gen_projection}

\section{Commuting Letters}

\input{comm}

\section{Conclusion}

We have continued the investigation of the state complexity of operations
on permutation automata, initiated in~\cite{DBLP:conf/dlt/HospodarM20},
and the investigation of the projection operation~\cite{DBLP:journals/tcs/JiraskovaM12,Wong98}.
We improved the general bound to the tight bound $2^{n - \lceil \frac{m}{2} \rceil} - 1$
in this case.
Note that the general bound $2^{n-1} + 2^{n-m} - 1$ for the projection
is only achieved for automata with precisely $m - 1$ non-loop unobservable transitions~\cite{DBLP:journals/tcs/JiraskovaM12}.
However, if we have more such unobservable transitions, then
it was also shown in~\cite{DBLP:journals/tcs/JiraskovaM12}
that we have the better tight bound $2^{n - 2} + 2^{n-3} + 2^{n - m} - 1$.
For our lower bound stated in Theorem~\ref{thm:lower_bound}
in the case of permutation automata, we have precisely
the same number of non-loop unobservable transitions as states incident
with them. 
Lastly, note that the condition in Proposition~\ref{prop:orbits_permuted}
could be easily checked. Likewise, checking if a subset of letters $\Delta$ generate a normal subgroup
could also be checked efficiently using results from~\cite{DBLP:conf/stoc/BabaiLS87}.


\smallskip \noindent \footnotesize
\textbf{Acknowledgement.} I sincerely thank the anonymous reviewers for careful reading and detailed feedback
that helped me in finding better formulations or fixing typos. Also, 
Section~\ref{sec:normal_subgroups} was restructured after this feedback and the cycle notation
was pointed out to me by one reviewer.

\bibliographystyle{splncs04}


\section{General Notions}
\label{subsec:general_notions}

By $\Sigma$ we denote a finite set of symbols, also called an \emph{alphabet}.
By $\Sigma^*$ we denote the set of all \emph{words} over $\Sigma$, i.e., finite sequences
with the concatenation operation. The \emph{empty word} is denoted by $\varepsilon$.
A \emph{language} $L$ is a subset $L \subseteq \Sigma^*$.
Languages using only a single symbol are called \emph{unary languages}.


If $X$ is a set, by $\mathcal P(X) = \{ Y \mid Y \subseteq X \}$ we denote the \emph{power set} of $X$.

If $x$ is a non-negative real number, by $\lceil x \rceil$ we denote the smallest natural number greater or equal to $x$
and by $\lfloor x \rfloor$ the largest natural number smaller or equal to $x$.


Let $\Gamma \subseteq \Sigma$. The homomorphism $\pi_{\Gamma} : \Sigma^* \to \Gamma^*$
given by $\pi_{\Gamma}(x) = x$ for $x \in \Gamma$
and $\pi_{\Gamma}(x) = \varepsilon$ for $x \in \Sigma \setminus \Gamma$
is called a \emph{projection (for $\Gamma$)}.
If $p,q \in Q$, $x \in \Sigma$, then
a transition $\delta(p, x) = q$ is said to be \emph{unobservable}
with respect to the projection $\pi_{\Gamma}$ if $x \in \Sigma \setminus \Gamma$, i.e., $\pi_{\Gamma}(x) = \varepsilon$.
Here, only non-loop 
unobservable transitions are of interest, i.e., those such that $p \ne q$.

A \emph{(partial) deterministic finite automaton (DFA)}
is denoted by a quintuple $\mathcal A =(Q, \Sigma, \delta, q_0, F)$,
where $Q$ is a \emph{finite set of states}, $\Sigma$ the \emph{input alphabet},
$\delta : Q \times \Sigma \to Q$ is a \emph{partial transition function},
$q_0$ the
\emph{start state} and $F \subseteq Q$ the set of \emph{final states}.
The DFA is said to be \emph{complete} if $\delta$ is a total function.
In the usual way, the transition function $\delta$
can be extended to a function $\hat \delta : Q \times \Sigma^* \to Q$ by setting, for $q \in Q$, $u \in \Sigma^*$
and $a \in \Sigma$, $\hat \delta(q, \varepsilon) = q$
and $\hat \delta(q, ua) = \delta(\hat \delta(q, u), a)$.
In the following, we drop the distinction between $\delta$ and $\hat \delta$
and denote both functions simply by $\delta$.


For $S \subseteq Q$ and $u \in \Sigma^*$, 
we set $\delta(S, u) = \{ \delta(s, u) \mid s \in S \mbox{ and } \delta(s, u) \mbox{ is defined} \}$.


The language \emph{recognized} by $\mathcal A$
is $L(\mathcal A) = \{ u \in \Sigma^* \mid \delta(q_0, u) \in F\}$.
A language $L \subseteq \Sigma^*$ is called \emph{regular}, if there exists an automaton $\mathcal A$
such that $L = L(\mathcal A)$.



For $u \in \Sigma^*$, we write $\delta(p, u) = \delta(q, u)$
if both are defined and the results are equal or both are undefined.


We say that $q$ is \emph{reachable} from $p$ (in $\mathcal A$)
if there exists a word $u \in \Sigma^*$ such that $\delta(p, u) = q$.
The DFA $\mathcal A$ is called \emph{initially connected}, if every state is reachable
from the start state.


The DFA $\mathcal A = (Q, \Sigma, \delta, q_0, F)$
is called \emph{commutative}, if, for each $a,b \in \Sigma$
and $q \in Q$, we have $\delta(q, ab) = \delta(q, ba)$.

Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a complete DFA.
For a word $u \in \Sigma^*$, the 
\emph{transition function (in $\mathcal A)$ associated to $u$}
is the function $\delta_u : Q \to Q$ 
given by $\delta_u(q) = \delta(q, u)$ for $q \in Q$.
The \emph{transformation monoid} is $\mathcal T_{\mathcal A} = \{ \delta_u \mid u \in \Sigma^* \}$.
Note that we defined the transformation monoid only for complete DFAs, as this is the only context
where we need this notion here.

To denote transitions in permutation DFAs, we use
a \emph{cycle notation} also used in~\cite{DBLP:journals/tcs/BrzozowskiS19,DBLP:conf/dlt/HospodarM20}.
More formally, $(q_1, \ldots, q_k)$ denotes the cyclic permutation
mapping $q_i$ to $q_{i+1}$ for $i \in \{1,\ldots,k-1\}$ and $q_k$ to $q_1$.
For example, $a = (1,2)(3,4,5)$ means the letter $a$ swaps the states $1$ and $2$,
cyclically permutes the states $3,4$ and $5$ in the indicated order and fixes all other states.




A \emph{variety (of formal languages)} $\mathcal V$~\cite{Eilenberg1976,Pin86,DBLP:reference/hfl/Pin97} associates,
to each alphabet $\Sigma$,
a class of recognizable
languages $\mathcal V(\Sigma^*)$ over $\Sigma$ such
that (1) $\mathcal V(\Sigma^*)$ is a boolean algebra,
(2) if $\varphi : \Sigma^* \to \Gamma^*$ is a homomorphism,
then $L \in \mathcal V(\Gamma^*)$
implies $\varphi^{-1}(L) \in \mathcal V(\Sigma^*)$
and (3) if $L \in \mathcal V(\Sigma^*)$ and $x \in \Sigma$,
then $\{ u \in \Sigma^* \mid xu \in L \}$
and $\{ u\in \Sigma^* \mid ux \in L \}$
are in $\mathcal V(\Sigma^*)$.

\begin{toappendix}

 \begin{remark}
 \label{rem:minimal_aut}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$. 
 Two states $p, q \in Q$
 are said to be \emph{distinguishable},
 if $\delta(p,u)$ and $\delta(q, u)$ 
 are not equal and there exists a word $u \in \Sigma^*$
 such that precisely one of the two states
 $\delta(p, u)$ or $\delta(q, u)$ is defined
 and final.
 A state is said to be \emph{coaccessible}, if a final state
 is reachable from it.
 The DFA $\mathcal A$ is the smallest DFA recognizing
 $L(\mathcal A)$, i.e., has the least number of states,
 if and only if every state is reachable from the start
 state, every two distinct states are distinguishable
 and every state is coaccessible~\cite{HopUll79}.
 We use this characterization
 later in proving our lower bound in Theorem~\ref{thm:lower_bound}.
 Note that if in a DFA $\mathcal A$
 every state is coaccessible,
 then for every non-empty subset $S \subseteq Q$ of states, we find
 a word $u \in \Sigma^*$ such that $\delta(S, u) \cap F \ne \emptyset$.
 This in particular implies that for the projection automaton, as its states are non-empty
 subsets of states, if we assume
 the input permutation automaton is initially connected, which also implies
 that every state is coaccessible for permutation automata\footnote{By Lemma~\ref{lem:inverses}, for every state of the form $q = \delta(q_0, u)$,
 there exists $u'$ such that $\delta(q_0, uu') = q_0$,
 and as $L(\mathcal A) \ne \emptyset$, there exists $w$
 such that $\delta(q_0, w) \in F$. Hence $\delta(q, u'w) \in F$
 and so, all states reachable from the start state are coaccessible.} 
 with $L(\mathcal A) \ne \emptyset$, 
 that 
 every state is coaccessible. So, we only
 need to show reachability and distinguishablity 
 in the proof of Theorem~\ref{thm:lower_bound}.
 \end{remark}
 
\end{toappendix}



\section{Orbit Sets, Projected Languages and Permutation Automata}
\label{subsec:orbitsets}



First, we introduce the orbit set of a set of states for a subalphabet. An orbit set collects those states that are reachable
from a given set of states by only using words from a given subalphabet.
This is also called \emph{unobservable reach} in~\cite{DBLP:books/daglib/0034521}.

\begin{definition}
\label{def:orbit}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a DFA.
 Suppose $\Sigma' \subseteq \Sigma$ and $S \subseteq Q$. The
 \emph{$\Sigma'$-orbit of $S$} is the set
 \[ 
  \operatorname{Orb}_{\Sigma'}(S) = \{ \delta(q, u) \mid \delta(q, u) \mbox{ is defined, } q \in S \mbox{ and } u \in \Sigma'^* \}.
 \]
 Also, for $q \in Q$, we set $\operatorname{Orb}_{\Sigma'}(q) = \operatorname{Orb}_{\Sigma'}(\{q\})$.
\end{definition}

 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a DFA
 and $\Gamma \subseteq \Sigma$.
 Set $\Delta = \Sigma \setminus \Gamma$.
 Next, we define the \emph{projection automaton} of $\mathcal A$
 for $\Gamma$ as
 $
 \mathcal R_{\mathcal A}^{\Gamma} = (\mathcal P(Q), \Gamma, \mu, \operatorname{Orb}_{\Delta}(q_0), E)
 $
 with, for $S \subseteq Q$ and $x \in \Gamma$, the transition function
  \begin{equation}\label{eqn:def_mu}
     \mu(S, x) = \operatorname{Orb}_{\Delta}(\delta(S, x))
 \end{equation}
 and

 $E = \{ T \subseteq Q \mid T \cap F \ne \emptyset \}$.
 In general, $\mathcal R_{\mathcal A}^{\Gamma}$
 is not initially connected. However, non-reachable states could be omitted. Actually, by the definition of the start state and transition function,
 we can restrict the state set to subsets of the form $\operatorname{Orb}_{\Delta}(S)$
 for $\emptyset \ne S \subseteq Q$.
 
 
 \begin{theoremrep}
  Let $\mathcal A$ be a DFA
  and $\Gamma \subseteq \Sigma$.
  Then, $\pi_{\Gamma}(L(\mathcal A)) = L(\mathcal R_{\mathcal A}^{\Gamma})$.
 \end{theoremrep}
 \begin{proof}
  
  Set $\Delta = \Sigma \setminus \Gamma$.
  Intuitively, we construct an $\varepsilon$-NFA for $\pi_{\Gamma}(L(\mathcal A))$
  from $\mathcal A$ by replacing all unobservable transitions
  with $\varepsilon$-transitions and determinize it, where
  the $\varepsilon$-closure of a subset of states corresponds
  to an $\Delta$-orbit.
  More formally, note that by Equation~\eqref{eqn:def_mu}
  and Definition~\ref{def:orbit},
  for $R \subseteq Q$, $q \in Q$ and $x \in \Sigma$,
  \[
   q \in \mu(R, x) \Leftrightarrow \exists p \in Q \ \exists y \in \Delta^* : p \in \delta(R, x) \land \delta(p, y) = q.
  \]
  and $q \in \operatorname{Orb}_{\Delta}(\{q_0\})$ if and only if
  there exists $y \in \Delta^*$ such that $\delta(q_0, y) = q$.
  Hence, we find, inductively, for every two states $p, q \in Q$ and $u \in \Gamma^*$, that
  $q \in \mu(\{p\}, u)$ if and only if, for $n = |u|$,
  there exist words $v_1, \ldots, v_n \in \Delta^*$,
  letters $x_1, \ldots x_n \in \Gamma$
  and states $p_0, p_1, \ldots, p_n \in Q$
  such that
  \begin{align*}
      p_0 & = p \\
      p_n & = q \\
      p_{i+1} & = \delta(p_i, x_{i+1} u_{i+1}) \mbox{ for } i \in \{0, \ldots,n-1\} \\
      u & = x_1 \cdots x_n.
  \end{align*}
  So, if $w \in \Gamma^*$, we can deduce that $\mu(\operatorname{Orb}_{\Delta}(\{q_0\}), w) \cap F \ne \emptyset$
  if and only if, for $n = |w|$,
  there exist words $v_0, v_1, \ldots, v_n \in \Delta^*$,
  letters $x_1, \ldots, x_n \in \Gamma$
  and states $p_0, p_1, \ldots, p_n$
  such that
   \begin{align*}
      p_0 & = \delta(q_0, v_0) \\
      p_n & \in F \\
      p_{i+1} & = \delta(p_i, u_i x_{i+1} u_{i+1}) \mbox{ for } i \in \{0, \ldots,n-1\} \\
      w & = x_1 \cdots x_n.
  \end{align*}
  Now, note that, $w \in \pi_{\Gamma}(L(\mathcal A))$
  is equivalent to the existence of $n \ge 0$ and a word $u \in L(\mathcal A)$
  that could be factorized into subwords $u_0, \ldots, u_n \in \Delta$
  and letters $x_1, \ldots, x_n \in \Gamma$
  such that $w = \pi_{\Gamma}(u_0 x_1 u_1 \cdots x_n u_n) = x_1 \cdots x_n$.
  This is equivalent to the above equations
  and so we find
  \[
   \mu(\operatorname{Orb}_{\Delta}(\{q_0\}), w) \cap F \ne \emptyset
   \Leftrightarrow \exists w \in \pi_{\Gamma}(L(\mathcal A)),
  \]
  or $L(\mathcal B) = \pi_{\Gamma}(L(\mathcal A))$.~\qed
 \end{proof}
 
 We do not introduce $\varepsilon$-NFAs formally here, but only refer to the literature~\cite{HopUll79}.
 However, we note in passing that, usually, an automaton for a projected language
 of a regular language is constructed by replacing the letters
 to be deleted by $\varepsilon$-transitions
 and then determinizing the resulting $\varepsilon$-NFA~\cite{HopUll79,DBLP:journals/tcs/JiraskovaM12}.
 Our construction is a more direct formulation of these steps, where the orbit
 sets are used in place of the $\varepsilon$-closure computations.
 
 
 In~\cite{DBLP:journals/tcs/JiraskovaM12,DBLP:conf/ifipTCS/JiraskovaM12}, an automaton was called a \emph{state-partition automaton}
 with respect to a projection $\pi_{\Gamma}$ (or, for short, a state-partition automaton for $\Gamma$),
 if the states of the resulting automaton from the above procedure, after discarding non-reachable subsets, form a partition of the original state set. 
 Hence, in our terminology, an automaton $\mathcal A$



 %

 is a state partition automaton if the reachable
 states of $\mathcal R_{\mathcal A}^{\Gamma}$
 form a partition of the states of $\mathcal A$.

 
 
A \emph{permutation automaton} (or \emph{permutation DFA}) is a DFA
$\mathcal A = (Q, \Sigma, \delta, q_0, F)$
such that every letter permutes the state set, i.e., the function $\delta_x : Q \to Q$
given by $\delta_x(q) = \delta(q, x)$ is a permutation, or bijection, of $Q$ for every $x \in \Sigma$. The languages recognized by permutation automata
are called \emph{group languages}. Note that permutation DFAs are complete DFAs.


The \emph{identity transformation (on $Q$)} is the permutation $\operatorname{id} : Q \to Q$
given by $\operatorname{id}(q) = q$ for each $q \in Q$.

 
 Next, we take a closer look at the orbit sets
 for permutation automata. But first, a general property of permutation
 automata.

\begin{lemmarep}
\label{lem:inverses}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a permutation automaton
 and $\Sigma' \subseteq \Sigma^*$.
 Then, for every $u \in \Sigma'^*$ there exists $u' \in \Sigma'^*$
 such that $\delta(q, uu') = q$ for each $q \in Q$, i.e,
 the word $uu'$ represents the identity transformation on $Q$.
\end{lemmarep}
\begin{proof}

 If $u \in \Sigma'^*$, define a function $\delta_u : Q \to Q$ by
 $\delta_u(q) = \delta(q, u)$.
 Then, $\delta_u$ is a permutation, and as $Q$ is finite, there
 exists $n > 0$ such that $\delta_u^n$ is the identity function, i.e.,
 $\delta_u^n(q) = q$ for each $q \in Q$.
 Then, $\delta(q, u^n) = q$ for each $q \in Q$
 and setting $u' = u^{n-1} \in \Sigma'^*$ gives the claim.~\qed
\end{proof}

 With the previous lemma, we can show that the orbit
 sets for permutation automata partition the state set.
 This property is crucial to derive our state complexity bound
 for projection, as it vastly reduces the possible
 subsets that are reachable in $\mathcal R_{\mathcal A}^{\Gamma}$, namely
 only unions of orbit sets.
 
\begin{lemmarep}
\label{lem:orbits-partition}
 Let $\mathcal A = (Q, \Sigma, \delta, q_0, F)$ be a permutation automaton.
 Suppose $\Sigma' \subseteq \Sigma$. Then, the sets $\operatorname{Orb}_{\Sigma'}(q)$, $q \in Q$,
 partition $Q$ and for every $S \subseteq Q$,
 $
  \operatorname{Orb}_{\Sigma'}(S) = \bigcup_{q \in S} \operatorname{Orb}_{\Sigma'}(q).
 $
\end{lemmarep}
\begin{proof}
  Clearly, we have $q \in \operatorname{Orb}_{\Sigma'}(q)$ for each $q \in Q$. 
  Suppose $q \in \operatorname{Orb}_{\Sigma'}(s) \cap \operatorname{Orb}_{\Sigma'}(t)$.
  Then, we first show $\operatorname{Orb}_{\Sigma'}(s) \subseteq \operatorname{Orb}_{\Sigma'}(t)$.
  Let $p \in \operatorname{Orb}_{\Sigma'}(s)$.
  By the previous assumptions, there exist $u, v, w \in \Sigma'^*$
  such that $q = \delta(s, u) = \delta(t, v)$
  and $p = \delta(s, w)$.
  By Lemma~\ref{lem:inverses}, we can choose $u' \in \Sigma'^*$
  such that $\delta(s, uu') = s$.
  So,
  \begin{align*}
      \delta(t, vu'w) & = \delta(\delta(t, v), u'w) \\ 
                      & = \delta(\delta(s, u), u'w) \\
                      & = \delta(\delta(s, uu'), w) \\
                      & = \delta(s, w) \\
                      & = p.
  \end{align*}
  Hence, $p \in \operatorname{Orb}_{\Sigma'}(t)$.
  As $p$ was chosen arbitrary, we find $\operatorname{Orb}_{\Sigma'}(s) \subseteq \operatorname{Orb}_{\Sigma'}(t)$.
  Similarly, we can show the other inclusion
  and hence $\operatorname{Orb}_{\Sigma'}(s) = \operatorname{Orb}_{\Sigma'}(t)$.
  
  
  If $\operatorname{Orb}_{\Sigma'}(q) \cap \operatorname{Orb}_{\Sigma'}(S) \ne \emptyset$,
  then there exists $s \in S$ such that $\operatorname{Orb}_{\Sigma'}(q) \cap \operatorname{Orb}_{\Sigma'}(s) \ne \emptyset$.
  So, by the previous claim, both $\Sigma'$-orbits are equal
  and we find $\operatorname{Orb}_{\Sigma'}(q) \subseteq \operatorname{Orb}_{\Sigma'}(S)$.
  By considering all elements in $S$, this yields $\bigcup_{q \in S} \operatorname{Orb}_{\Sigma'}(q) = \operatorname{Orb}_{\Sigma'}(S)$.~\qed
\end{proof}



