text:
\section{\texorpdfstring{$3$-compressible automata without permutations}{3-compressible automata without permutations}}\label{nopermutation}

In this section we characterize proper $3$-compressible automata on $2$-letter alphabet where no letter acts as permutation.

\begin{proposition}\label{proposition:1-2-4}
Let $\A$ a $(\bf{i},\bf{j})$-automaton with $i\in\{1,2\}$ and $j\in\{1,2,4\}$, then $\A$ is either not $3$-compressible or not proper.
\end{proposition}

\begin{proof}
We have to consider five different cases.
\begin{enumerate}
  \item Let $\A$ be a $(\bf{1},\bf{1})$-automaton with $a=[1,2,3]\backslash 1,2$ and $b=[x,y,z]\backslash x,y$:
      \begin{enumerate}
        \item if $\{1,2\}\subseteq\{x,y,z\}$ and $\{x,y\}\subseteq\{1,2,3\}$, then for any $w\in\{a,b\}^*$, we have $\M(wa)=\{1,2\}$ and $\M(wb)=\{x,y\}$, so $\A$ is not 3-compressible;
        \item if $\{1,2\}\nsubseteq\{x,y,z\}$, then $|\M(ab)|\geq 3$, so $\A$ is not proper; similarly if $\{x,y\}\nsubseteq\{1,2,3\}$, then $|\M(ba)|\geq 3$, and again $\A$ is not proper.
      \end{enumerate}
  \item Let $\A$ be a $(\bf{1},\bf{2})$-automaton with $a=[1,2,3]\backslash 1,2$ and $b=[x,y][z,v]\backslash x,z$:
      \begin{enumerate}
        \item if $\{1,2\}\in\{\{x,z\},\{x,v\},\{y,z\},\{y,v\}\}$ and $\{x,z\}\subseteq\{1,2,3\}$, then for any $w\in\{a,b\}^*$, we have $\M(wa)=\{1,2\}$ and $\M(wb)=\{x,z\}$, so $\A$ is not $3$-compressible;
        \item if $\{1,2\}\not\in\{\{x,z\},\{x,v\},\{y,z\},\{y,v\}\}$, then $|\M(ab)|\geq 3$, so $\A$ is not proper; similarly if $\{x,z\}\nsubseteq\{1,2,3\}$, then $|\M(ba)|\geq 3$, and again $\A$ is not proper.
      \end{enumerate}
  \item Let $\A$ be a $(\bf{2},\bf{2})$-automaton with $a=[1,2][3,4]\backslash 1,3$ and $b=[x,y][z,v]\backslash x,z$:
      \begin{enumerate}
        \item if $\{1,3\}\in\{\{x,z\},\{x,v\},\{y,z\},\{y,v\}\}$ and $\{x,z\}\in\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$, then for all $w\in\{a,b\}^*$, we have $\M(wa)=\{1,3\}$ and $\M(wb)=\{x,z\}$, so $\A$ is not $3$-compressible;
        \item if $\{1,3\}\not\in\{\{x,z\},\{x,v\},\{y,z\},\{y,v\}\}$, then $|\M(ab)|\geq 3$, so $\A$ is not proper; similarly if $\{x,z\}\not\in\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$, then $|\M(ba)|\geq 3$, and again $\A$ is not proper.
      \end{enumerate}
  \item Let $\A$ be a $(\bf{1},\bf{4})$-automaton with $a=[1,2,3]\backslash 1,2$ and $b=[x,y]\backslash z$, $zb=x$:
      \begin{enumerate}
        \item if $\{x,z\}\nsubseteq\{1,2,3\}$, then $\M(b^2)=\{x,z\}$ and $\M(b^2a)=\{1,2,xa,za\}$, so $\A$ is not proper;
        \item if $\{x,z\}=\{1,2\}$, then for all $w\in\{a,b\}^+\setminus\{b\}$, we have $\M(w)=\{1,2\}$, so $\A$ is not $3$-compressible;
        \item if $\{x,z\}\in\{\{1,3\},\{2,3\}\}$, let $q\in\{1,2,3\}\setminus\{x,z\}$. Then $\M(ab)=\{z,qb\}$ and $\M(ab^2)=\{x,z,qb^2\}$, so $\A$ is not proper.
      \end{enumerate}
  \item Let $\A$ be a $(\bf{2},\bf{4})$-automaton with $a=[1,2][3,4]\backslash 1,3$ and $b=[x,y]\backslash z$, $zb=x$:
      \begin{enumerate}
        \item if $\{x,z\}\not\in\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$, then $\M(b^2)=\{x,z\}$ and $|\M(b^2a)|\geq 3$, so $\A$ is not proper;
        \item if $\{x,y\}\cap\{1,3\}=\emptyset$, then $\M(ab)=\{1b,3b,z\}$, so $\A$ is not proper;
        \item if $\{x,z\}=\{1,3\}$, then for all $w\in\{a,b\}^+\setminus\{b\}$, we have $\M(w)=\{1,3\}$, so $\A$ is not $3$-compressible;
        \item if $\{x,z\}=\{1,4\}$ and $\{x,y\}\cap\{1,3\}\neq\emptyset$, we consider two subcases:
          \begin{enumerate}
            \item if $x=4$ and $z=1$, then $y$ must be equal to 3. So $b=[4,3]\backslash 1$, then for all $w\in\{a,b\}^+$, we have $\M(wa)=\{1,3\}$ and $\M(wb)=\{1,4\}$, so $\A$ is not $3$-compressible;
            \item if $x=1$ and $z=4$, then if $y\neq 2$ the P3MSA in Fig. \ref{fig:caso:2-4:1-4:2} proves that $\A$ is not proper. Else, if $y=2$ and $3b\neq 2$, then the word $aba$ $3$-compresses $\A$ which is not proper. Otherwise, if $y=2$ and $3b=2$, then the 3MSA in Fig. \ref{fig:caso:2-4:1-4} proves that $\A$ is not $3$-compressible;
          \end{enumerate}
        \item if $\{x,z\}=\{2,3\}$, this case reduces to the previous exchanging the state $1$ with $3$ and $2$ with $4$;
        \item if $\{x,z\}=\{2,4\}$ and $\{x,y\}\cap\{1,3\}\neq\emptyset$ then $y\in\{1,3\}$. Let $q\in\{1,3\}\setminus\{y\}$.
            \begin{enumerate}
              \item If $b=[2,1]\backslash 4$ and $q=3$, or $b=[4,3]\backslash 2$ and $q=1$ then, if $qb\neq y$ we have $\M(ab)=\{z,qb\}$ and $\M(aba)=\{1,3,qba\}$, so the automaton is not proper, else if $qb=y$ $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:caso:2-4:2-4:1}.
              \item Let $b=[2,3]\backslash 4$ and $q=1$, or $b=[4,1]\backslash 2$ and $q=3$ then either the word $ab^2$ or $aba$ $3$-compresses $\A$, so it is not proper.
                  \begin{figure}[ht]
                    \centering
                    \subfigure[][P3MSA for the case $b={[1,y]}\backslash 4$, $4b=1$, $y\neq 2$.]{
                    \label{fig:caso:2-4:1-4:2}
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$1,3$};
                        \node[state] (q_3) [right=4.5em of q_1] {$4,3b$};
                        \node[state] (q_4) [below of= q_1] {$2,4$};
                        \node[state,accepting] (q_5) [below of= q_3] {};

                        \path[->] (q_0) edge node {$a$} (q_1)
                                  (q_1) edge node {$b|3b\neq 2$} (q_3)
                                  (q_1) edge node {$b|3b=2$} (q_4)
                                  (q_3) edge node {$a$} (q_5)
                                  (q_4) edge node {$b$} (q_5);

                        \draw [->] (-.5,.5) -- (-.27,.27);

                    \end{tikzpicture}}}
                    \hspace{30pt}
                    \subfigure[][3MSA for the case $b={[1,2]}\backslash 4$, $4b=1$, $3b=2$, or $b={[2,1]}\backslash 4$, $4b=1$ and $3b= 1$, or $b={[4,3]}\backslash 2$, $2b=4$ and $1b= 3$.]{
                    \label{fig:caso:2-4:2-4:1}
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$1,3$};
                        \node[state] (q_2) [right of= q_1] {$y,z$};
                        \node[state] (qq) [draw=none,right=8.1em of q_1] {};
                        \node[state] (q_3) [below of= q_0] {$z$};
                        \node[state] (q_4) [below of= q_1] {$x,z$};
                        \node[state,draw=none] (q) [right of= q_3] {};

                        \path[->] (q_0) edge node {$a$} (q_1)
                                  (q_0) edge node {$b$} (q_3)
                                  (q_1) edge [loop above] node {$a$} (q_1)
                                  (q_1) edge [bend left=10] node {$b$} (q_2)
                                  (q_2) edge node {$b$} (q_4)
                                  (q_2) edge [bend left=10] node {$a$} (q_1)
                                  (q_3) edge node {$b$} (q_4)
                                  (q_3) edge node {$a$} (q_1)
                                  (q_4) edge [loop right] node {$b$} (q_4)
                                  (q_4) edge node {$a$} (q_1);

                        \draw [->] (-.5,.5) -- (-.27,.27);

                    \end{tikzpicture}}}
                    \caption[]{3MSA for a $(\bf{2},\bf{4})$-automaton with $a=[1,2][3,4]\backslash 1,3$ and $b$ satisfying either condition (d).ii or (f).i.}
                    \label{fig:caso:2-4:1-4}
                \end{figure}
            \end{enumerate}
      \end{enumerate}
\end{enumerate}
\end{proof}

\FloatBarrier

\begin{proposition}\label{proposition:1-3}
Let $\A$ be a $(\bf{1},\bf{3})$-automaton with $a=[1,2,3]\backslash 1,2$ and $b=[x,y]\backslash x$.
Then $\A$ is $3$-compressible and proper if, and only if, the following conditions hold:
\begin{enumerate}
  \item $x\in\{1,2,3\}$, and
  \item $\{1,2\}\cap\{x,y\}\neq\emptyset$, and
  \item for all $q\in\{1,2\}\setminus\{x\}$, $qb\in\{1,2,3\}$, and $Orb_b(q)\not\subseteq\{1,2,3\}$.
\end{enumerate}
Moreover, if $\mathcal{A}$ is proper and $3$-compressible, then the word $ab^2a$ $3$-compresses $\A$.
\end{proposition}

\begin{proof}
Let $\A$ be a $(\bf{1},\bf{3})$-automaton that does not satisfy one of the conditions $1.-3.$
\begin{enumerate}
  \item Let $x\not\in\{1,2,3\}$, then the word $ba$ $3$-compresses $\A$, and so it is not proper.
  \item Let $\{1,2\}\cap\{x,y\}=\emptyset$, then the word $ab$ $3$-compresses $\A$, and so it is not proper.
  \item Let for all $q\in\{1,2\}\setminus\{x\}$ be $qb\not\in\{1,2,3\}$ or $Orb_b(q)\subseteq\{1,2,3\}$, and $x\in\{1,2,3\}$, and $\{1,2\}\cap\{x,y\}\neq\emptyset$.
      \begin{enumerate}
        \item Let $qb\not\in\{1,2,3\}$, then if $x\in\{1,2\}$, we have $\M(ab)=\{qb,x\}$ and $\M(aba)=\{1,2,qba\}$, else if $x=3$, we choose $q\in\{1,2\}\setminus\{y\}$, and again $\M(ab)=\{qb,x\}$ and $\M(aba)=\{1,2,qba\}$.
            So if $qb\not\in\{1,2,3\}$ the word $aba$ $3$-compresses $\A$ which is not proper.
        \item So let $qb\in\{1,2,3\}$ and $Orb_b(q)\subseteq\{1,2,3\}$.
            \begin{enumerate}
                \item If $x\in\{1,2\}$, then $qb\in\{q,3\}$ and $3b=q$, so $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:prop:1-3:1}.
                \item If $x=3$, then $y\in\{1,2\}$ and $\{1b,2b\}=\{1,2\}$, and $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:prop:1-3:2}, where in this case $q\in\{1,2\}\setminus\{y\}$.
            \begin{figure}[ht]
                \centering
                \subfigure[][3MSA for the case $x\in\{1,2\}$.]{
                \label{fig:prop:1-3:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$1,2$};
                    \node[state] (q_2) [right of= q_1,draw=none] {};
                    \node[state] (q_3) [right of= q_2] {$x,3$};
                    \node[state] (q_4) [below of= q_0] {$x$};
                    \node[state] (q_5) [right of= q_4] {$1,2$};
                    \node[state] (q_6) [right of= q_5] {$x,q$};
                    \node[state] (q_7) [right of= q_6] {$1,2$};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_4)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge node {$b|qb=3$} (q_3)
                              (q_1) edge node {$b|qb=q$} (q_5)
                              (q_3) edge [bend left=10] node {$a$} (q_7)
                              (q_3) edge [bend left=10] node {$b$} (q_6)
                              (q_4) edge [loop below] node {$b$} (q_4)
                              (q_4) edge node {$a$} (q_1)
                              (q_5) edge [loop below] node {$a,b$} (q_5)
                              (q_6) edge node {$a$} (q_7)
                              (q_6) edge [bend left=10] node {$b$} (q_3)
                              (q_7) edge [bend left=10] node {$b$} (q_3)
                              (q_7) edge [loop below] node {$a$} (q_7);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                }
                \hspace{20pt}
                \subfigure[][3MSA for the case $x=3$.]{
                \label{fig:prop:1-3:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$1,2$};
                    \node[state] (q_2) [right of= q_1,draw=none] {};
                    \node[state] (q_3) [right of= q_2] {$3,q$};
                    \node[state] (q_4) [right of= q_3] {$1,2$};
                    \node[state] (q_5) [below of= q_0] {$1$};
                    \node[state] (q_6) [right of= q_5] {$3,q$};
                    \node[state] (q_7) [right of= q_6] {$3,y$};
                    \node[state] (q_8) [right of= q_7] {$1,2$};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_5)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge node {$b|qb=q$} (q_3)
                              (q_1) edge node {$b|qb=y$} (q_7)
                              (q_3) edge [loop above] node {$b$} (q_3)
                              (q_3) edge [bend left=10] node {$a$} (q_4)
                              (q_4) edge [loop above] node {$a$} (q_4)
                              (q_4) edge [bend left=10] node {$b$} (q_3)
                              (q_5) edge [loop below] node {$b$} (q_5)
                              (q_5) edge node {$a$} (q_1)
                              (q_6) edge [bend right=35] node [swap] {$a$} (q_8)
                              (q_6) edge [bend left=10] node {$b$} (q_7)
                              (q_7) edge [bend left=10] node {$b$} (q_6)
                              (q_7) edge [bend left=10] node {$a$} (q_8)
                          (q_8) edge [loop below] node {$a$} (q_8)
                          (q_8) edge [bend left=10] node {$b$} (q_7)

                          (q_6) edge [loop below,draw=none] node {\phantom{$a,b$}} (q_6);

                \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \caption[]{3MSA for automata that do not satisfy condition 3. of Proposition \ref{proposition:1-3} with $zb\in\{1,2,3\}$ and $Orb_b(z)\subseteq\{1,2,3\}$.}
                \label{fig:prop:1-3}
            \end{figure}
            \end{enumerate}
        \end{enumerate}
\end{enumerate}
Conversely, suppose $x\in\{1,2,3\}$, $\{1,2\}\cap\{x,y\}\neq\emptyset$, and for all $q\in\{1,2\}\setminus\{x\}$, $qb\in\{1,2,3\}$ and $Orb_b(q)\not\subseteq\{1,2,3\}$.
If $x\in\{1,2\}$, let $q\in\{1,2\}\setminus\{x\}$, else let $q\in\{1,2\}\setminus\{y\}$; then $\M(ab)=\{x,qb\}$, $\M(ab^2)=\{x,qb^2\}$, and, as $qb^2\not\in\{1,2,3\}$, $\M(ab^2a)=\{1,2,qb^2a\}$, and the word $ab^2a$ $3$-compresses $\A$.
\end{proof}

\FloatBarrier

\begin{proposition}\label{proposition:2-3}
Let $\A$ be a $(\bf{2},\bf{3})$-automaton with $a=[1,2][3,4]\backslash 1,3$ and $b=[x,y]\backslash x$. Then $\A$ is $3$-compressible and proper if, and only if, the following conditions hold:
\begin{enumerate}
  \item $x\in\{1,2,3,4\}$, and
  \item if $x=1$, then $3b=4$ and $Orb_b(3)\not\subseteq\{3,4\}$, and
  \item if $x=2$, then $y\in\{1,3\}$ and
  \begin{enumerate}
    \item if $y=1$, then $3b=4$ and $4b\neq 3$, and
    \item if $y=3$, then $1b\in\{3,4\}$, and
  \end{enumerate}
  \item if $x=3$, then $1b=2$ and $Orb_b(1)\not\subseteq\{1,2\}$, and
  \item if $x=4$, then $y\in\{1,3\}$ and
  \begin{enumerate}
    \item if $y=1$, then $3b\in\{1,2\}$, and
    \item if $y=3$, then $1b=2$ and $2b\neq 1$.
  \end{enumerate}
\end{enumerate}
Moreover, if $\mathcal{A}$ is proper and $3$-compressible, then either the word $ab^2a$ or $ab^3a$ $3$-compresses $\A$.
\end{proposition}

\begin{proof}
Let $\A$ be a $(\bf{2},\bf{3})$-automaton that does not satisfy one of the conditions $1.-5.$
\begin{enumerate}
  \item Let $x\not\in\{1,2,3,4\}$, then the word $ba$ $3$-compresses $\A$, and so it is not proper.
  \item Let $x=1$,
  \begin{enumerate}
    \item if $3b\neq 4$, then if $3b=3$ $\A$ is not $3$-compressible, while if $3b\neq 3$ the word $aba$ $3$-compresses $\A$ that it is not proper, as shown in Fig. \ref{fig:prop:2-3:2:1};
    \item if $3b=4$ and $Orb_b(3)\subseteq\{3,4\}$, then $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:prop:2-3:2:2}.
        \begin{figure}[ht]
            \centering
            \subfigure[][Case $3b\neq 4$.]{
            \label{fig:prop:2-3:2:1}
            {\footnotesize
            \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                \node[state] (q_0) {};
                \node[state] (q_1) [right of= q_0] {$1,3$};
                \node[state] (q_2) [right of= q_1,draw=none] {};
                \node[state] (q_3) [right of= q_2] {$1,3$};
                \node[state] (q_4) [below of= q_0] {$1$};
                \node[state] (q_5) [below of= q_2] {$1,3b$};
                \node[state,accepting] (q_6) [right of= q_5] {};
                \node[state,draw=none] (q_7) [right of= q_6] {};

                \path[->] (q_0) edge node {$a$} (q_1)
                          (q_0) edge node {$b$} (q_4)
                          (q_1) edge [loop above] node {$a$} (q_1)
                          (q_1) edge node {$b|3b=3$} (q_3)
                          (q_1) edge node {$b|3b\neq 3$} (q_5)
                          (q_3) edge [loop above] node {$a,b$} (q_3)
                          (q_4) edge [loop left] node {$b$} (q_4)
                          (q_4) edge node {$a$} (q_1)
                          (q_5) edge node {$a$} (q_6);

                \draw [->] (-.5,.5) -- (-.27,.27);

            \end{tikzpicture}}
            }
            \hspace{20pt}
            \subfigure[][Case $Orb_b(3)\subseteq\{3,4\}$ and $3b=4$.]{
            \label{fig:prop:2-3:2:2}
            {\footnotesize
            \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                \node[state] (q_0) {};
                \node[state] (q_1) [right of= q_0] {$1,3$};
                \node[state] (q_2) [right of= q_1] {$1,4$};
                \node[state] (q_3) [right of= q_2,draw=none] {};
                \node[state] (q_4) [below of= q_0] {$1$};

                \path[->] (q_0) edge node {$a$} (q_1)
                          (q_0) edge node {$b$} (q_4)
                          (q_1) edge [loop above] node {$a$} (q_1)
                          (q_1) edge [bend left=10] node {$b$} (q_2)
                          (q_2) edge [bend left=10] node {$a,b$} (q_1)
                          (q_4) edge [loop left] node {$b$} (q_4)
                          (q_4) edge node {$a$} (q_1);

                \draw [->] (-.5,.5) -- (-.27,.27);

            \end{tikzpicture}}}
            \caption[]{3MSA for automata that do not satisfy condition $2.$ of Proposition \ref{proposition:2-3}.}
            \label{fig:prop:2-3:2}
        \end{figure}
  \end{enumerate}
  \item Let $x=2$,
      \begin{enumerate}
        \item if $y\not\in\{1,3\}$, then the word $ab$ $3$-compresses $\A$, and so it is not proper;
        \item if $y=1$, then if $3b\neq 4$, then $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:prop:2-3:3:1}; while if $3b=4$ and $4b=3$, then $\A$ is not $3$-compressible, as shown in Fig. \ref{fig:prop:2-3:3:2};
            \begin{figure}[ht]
                \centering
                \subfigure[][Case $3b\neq 4$.]{
                \label{fig:prop:2-3:3:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$1,3$};
                    \node[state] (q_2) [right of= q_1,draw=none] {};
                    \node[state] (q_3) [right of= q_2] {$2,3$};
                    \node[state] (q_4) [below of= q_0] {$2$};
                    \node[state] (q_5) [below of= q_2] {$2,3b$};
                    \node[state,accepting] (q_6) [right of= q_5] {};
                    \node[state] (q_7) [right of= q_3] {$1,3$};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_4)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge node {$b|3b=3$} (q_3)
                              (q_1) edge node {$b|3b\neq 3$} (q_5)
                              (q_3) edge [loop above] node {$b$} (q_3)
                              (q_3) edge [bend left=10] node {$a$} (q_7)
                              (q_7) edge [bend left=10] node {$b$} (q_3)
                              (q_7) edge [loop above] node {$a$} (q_7)
                              (q_4) edge [loop left] node {$b$} (q_4)
                              (q_4) edge node {$a$} (q_1)
                              (q_5) edge node {$a$} (q_6);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                }
                \hspace{20pt}
                \subfigure[][Case $3b=4$ and $4b=3$.]{
                \label{fig:prop:2-3:3:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$1,3$};
                    \node[state] (q_2) [right of= q_1] {$2,4$};
                    \node[state] (q_3) [right of= q_2] {$2,3$};
                    \node[state] (q_4) [below of= q_0] {$2$};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_4)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge [bend left=10] node {$b$} (q_2)
                              (q_2) edge [bend left=10] node {$b$} (q_3)
                              (q_2) edge [bend left=10] node {$a$} (q_1)
                              (q_3) edge [bend left=30] node {$a$} (q_1)
                              (q_3) edge [bend left=10] node {$b$} (q_2)
                              (q_4) edge [loop left] node {$b$} (q_4)
                              (q_4) edge node {$a$} (q_1);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \caption[]{3MSA for automata that do not satisfy condition $3.$ of Proposition \ref{proposition:2-3} with $y=1$.}
                \label{fig:prop:2-3:3}
            \end{figure}
        \item if $y=3$ and $1b\not\in\{3,4\}$, then $\M(ab)=\{2,1b\}$, and $\M(aba)=\{1,3,1ba\}$, so the word $aba$ $3$-compresses $\A$ that it is not proper.
      \end{enumerate}
\end{enumerate}
The cases $x=3$ and $x=4$ reduce to case $2.$ and $3.$, respectively.

Conversely, suppose $x\in\{1,2,3,4\}$.
\begin{enumerate}
  \item Let $x=1$, $3b=4$ and $Orb_b(3)\not\subseteq\{3,4\}$, this implies $4b=3b^2\not\in\{3,4\}$. Then $\M(ab)=\{1,4\}$, $\M(ab^2)=\{1,4b\}$ and $\M(ab^2a)=\{1,3,4ba\}$, so $ab^2a$ $3$-compresses $\A$.
  \item Let $x=2$.
    \begin{enumerate}
      \item If $y=1$, $3b=4$ and $4b\neq 3$, then $\M(ab)=\{2,4\}$, $\M(ab^2)=\{2,4b\}$ and $\M(ab^2a)=\{1,3,4ba\}$, so $ab^2a$ $3$-compresses $\A$.
      \item If $y=3$ and $1b\in\{3,4\}$, then either the word $ab^2a$ or $ab^3a$ $3$-compresses $\A$, as shown in Fig. \ref{fig:prop:2-3:r}.
          \begin{figure}[ht]
            \centering
            {\footnotesize
            \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                \node[state] (q_0) {};
                \node[state] (q_1) [right of= q_0] {$1,3$};
                \node[state] (q_2) [right of= q_1] {$2,1b$};
                \node[state] (q_3) [right of= q_2] {$2,1b^2$};
                \node[state,draw=none] (q_4) [right of= q_3] {};
                \node[state] (q_5) [right of= q_4] {$2,1b^3$};
                \node[state,accepting] (q_6) [right of= q_5] {};

                \path[->] (q_0) edge node {$a$} (q_1)
                          (q_1) edge node {$b$} (q_2)
                          (q_2) edge node {$b$} (q_3)
                          (q_3) edge node {$b|1b^2\in\{3,4\}$} (q_5)
                          (q_3) edge [bend right=25] node [swap] {$b|1b^2\not\in\{3,4\}$} (q_6)
                          (q_5) edge node {$a$} (q_6);

                \draw [->] (-.5,.5) -- (-.27,.27);

            \end{tikzpicture}}\\
            \caption[]{P3MSA for the case $b=[2,3]\backslash 2$ and $1b\in\{3,4\}$.}
            \label{fig:prop:2-3:r}
            \end{figure}
    \end{enumerate}
\end{enumerate}
The cases $x=3$ and $x=4$ reduce to cases $1.$ and $2.$, respectively.
\end{proof}

\FloatBarrier

The following lemma is straightforward.
\begin{lemma}\label{lemma:3-3:0}
Let $\A$ be a $(\bf{3},\bf{3})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash x$.
Then $x\neq 1$ and $\{x,y\}\neq \{1,2\}$.
\end{lemma}

\begin{lemma}\label{lemma:3-3:1}
Let $\A$ be a $(\bf{3},\bf{3})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[2,y]\backslash 2$ with $y\neq 1$.
Then:
\begin{enumerate}
  \item $\{1ba,1b^2a,1b^3a\}\not\subseteq\{2,y\}$, or
  \item $Orb_a(1ba)\not\subseteq\{2,y\}$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\A$ be a $(\bf{3},\bf{3})$-automaton that does not satisfy the above conditions, we prove that it is not $3$-compressible or not proper.
\begin{enumerate}
  \item Let $1b=1$ and $Orb_a(1ba)\subseteq\{2,y\}$.
      \begin{enumerate}
        \item If $1ba=1a=2a=2$, then the 3MSA in Fig. \ref{fig:lemma:3-3:1:1:1} proves that $\A$ is not 3-compressible;
        \item If $1ba=1a=2a=y$, then $ya=1ba^2=2$ and the 3MSA in Fig. \ref{fig:lemma:3-3:1:1:2} proves that $\A$ is not 3-compressible.
            \begin{figure}[ht]
                \centering
                \subfigure[][Case $1a=2$.]{
                \label{fig:lemma:3-3:1:1:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_1] {$1$};
                    \node[state] (q_3) [right of= q_2] {$1,2$};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_0) edge [bend right=30] node [swap] {$a$} (q_2)
                              (q_1) edge node {$a$} (q_2)
                              (q_1) edge [loop above] node {$b$} (q_1)
                              (q_2) edge node {$b$} (q_3)
                              (q_2) edge [loop above] node {$a$} (q_2)
                              (q_3) edge [loop above] node {$a,b$} (q_3);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                }
                \hspace{20pt}
                \subfigure[][Case $1a=y$.]{
                \label{fig:lemma:3-3:1:1:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_1] {$1$};
                    \node[state] (q_3) [right of= q_2] {$1,2$};
                    \node[state] (q_4) [right of= q_3] {$1,y$};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_0) edge [bend right=30] node [swap] {$a$} (q_2)
                              (q_1) edge node {$a$} (q_2)
                              (q_1) edge [loop above] node {$b$} (q_1)
                              (q_2) edge node {$b$} (q_3)
                              (q_2) edge [loop above] node {$a$} (q_2)
                              (q_3) edge [loop above] node {$b$} (q_3)
                              (q_3) edge [bend left=10] node {$a$} (q_4)
                              (q_4) edge [bend left=10] node {$a,b$} (q_3);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \caption[]{3MSA for automata that do not satisfy conditions 1. and 2. of Lemma \ref{lemma:3-3:1} with $1b=1$.}
                \label{fig:lemma:3-3:1:1}
            \end{figure}
      \end{enumerate}
  \item Let $1b\neq1$, $\{1ba,1b^2a,1b^3a\}\subseteq\{2,y\}$ and $Orb_a(1ba)\subseteq\{2,y\}$.
      If $1ba=1b^2a$ or $1b^2a=1b^3a$, then for all $h>0$ $1b^h\neq 2$, then $1=1b$, against the hypothesis.
      If $1b^2a=1b^3a$, as $1b^2\neq 2$, then $1b^2=1b^3$, and then $1=1b$, against the hypothesis.
      So, as $|\{1ba,1b^2a,1b^3a\}|\leq 2$, $1ba=1b^3a$, then $1b=1b^3$ and $1=1b^2$.
      \begin{enumerate}
        \item If $1ba=2$, then $1b^2a=y$, hence $1a=2a=y$, $ya=2$ and $1b=y$.
            The 3MSA in Fig. \ref{fig:lemma:3-3:1:2:1} proves that $\A$ is not 3-compressible;
        \item If $1ba=y$, then $1b^2a=1a=2a=2$.
            Moreover, $1ba^2=y$, otherwise $1ba^2=2$ gives the contradiction $1ba=1$, hence $ya=y$, $1b=y$ and $yb=1b^2=1$.
            The 3MSA in Fig. \ref{fig:lemma:3-3:1:2:2} proves that $\A$ is not 3-compressible.
            \begin{figure}[ht]
                \centering
                \subfigure[][Case $1ba=2$.]{
                \label{fig:lemma:3-3:1:2:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [below of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_0] {$1$};
                    \node[state] (q_3) [right of= q_2] {$y,2$};
                    \node[state] (q_4) [right of= q_3] {$1,2$};
                    \node[state] (q_5) [below of= q_3] {$1,y$};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_0) edge node {$a$} (q_2)
                              (q_1) edge node [swap] {$a$} (q_2)
                              (q_1) edge [loop right] node {$b$} (q_1)
                              (q_2) edge node {$b$} (q_3)
                              (q_2) edge [loop above] node {$a$} (q_2)
                              (q_3) edge [bend left=10] node {$a,b$} (q_4)
                              (q_4) edge [bend left=10] node {$a$} (q_5)
                              (q_4) edge [bend left=10] node {$b$} (q_3)
                              (q_5) edge [bend left=10] node {$a$} (q_4)
                              (q_5) edge node {$b$} (q_3);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                }
                \hspace{20pt}
                \subfigure[][Case $1ba=y$.]{
                \label{fig:lemma:3-3:1:2:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [below of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_0] {$1$};
                    \node[state] (q_4) [right of= q_2] {$y,2$};
                    \node[state] (q_3) [below of= q_4] {$1,2$};
                    \node[state] (q_5) [right of= q_4] {$1,y$};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_0) edge node {$a$} (q_2)
                              (q_1) edge node [swap] {$a$} (q_2)
                              (q_1) edge [loop right] node {$b$} (q_1)
                              (q_2) edge node {$b$} (q_4)
                              (q_2) edge [loop above] node {$a$} (q_2)
                              (q_3) edge [loop right] node {$a$} (q_3)
                              (q_3) edge [bend left=10] node {$b$} (q_4)
                              (q_4) edge [bend left=10] node {$a$} (q_5)
                              (q_4) edge [bend left=10] node {$b$} (q_3)
                              (q_5) edge [loop above] node {$a$} (q_5)
                              (q_5) edge [bend left=10] node {$b$} (q_4);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \caption[]{3MSA for automata that do not satisfy conditions 1. and 2. of Lemma \ref{lemma:3-3:1} with $1b\neq1$.}
                \label{fig:lemma:3-3:1:2}
            \end{figure}
      \end{enumerate}
\end{enumerate}
\end{proof}

\begin{corollary}\label{corollary:3-3:1}
Let $\A$ be a $(\bf{3},\bf{3})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[x,1]\backslash x$ with $x\neq 2$.
Then:
\begin{enumerate}
  \item $\{xab,xa^2b,xa^3b\}\not\subseteq\{1,2\}$, or
  \item $Orb_b(xab)\not\subseteq\{1,2\}$.
\end{enumerate}
\end{corollary}

\begin{proof}
It is a straightforward consequence of the previous lemma, simply replacing $a$ with $b$, 1 with 2, 2 with $y$ and $x$ with 1.
\end{proof}

\begin{lemma}\label{lemma:3-3:2}
Let $\A$ be a proper $(\bf{3},\bf{3})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash x$ with $x\not\in\{1,2\}$ and $y\neq 1$.
Then all the following conditions hold:
\begin{enumerate}
  \item $1b\in\{1,2\}$, and
  \item $xa\in\{x,y\}$, and
  \item $Orb_b(1)\not\subseteq\{1,2\}$ or $Orb_a(x)\not\subseteq\{x,y\}$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\A$ be a $(\bf{3},\bf{3})$-automaton that does not satisfy the above conditions, we prove that it is not $3$-compressible or not proper.
\begin{enumerate}
  \item If $1b\not\in\{1,2\}$, then $\A$ is not proper, in fact $\M(ab)=\{x,1b\}$ and $|\M(aba)|=3$; similarly
  \item if $1b\in\{1,2\}$ and $xa\not\in\{x,y\}$, then $\A$ is not proper, in fact $\M(ba)=\{1,xa\}$ and $|\M(bab)|=3$.
  \item If $1b\in\{1,2\}$, $xa\in\{x,y\}$, $Orb_b(1)\subseteq\{1,2\}$ and $Orb_a(x)\subseteq\{x,y\}$, then
      \begin{enumerate}
        \item if $1b=1$ and $xa=x$, the 3MSA of $\A$ is in Fig. \ref{fig:lemma:3-3:2:2:1};
        \item $1b=1$ and $xa=y$ (and then $ya=x$), the 3MSA of $\A$ is in Fig. \ref{fig:lemma:3-3:2:2:2};
        \item $1b=2$ (and then $2b=1$) and $xa=x$, the 3MSA of $\A$ is in Fig. \ref{fig:lemma:3-3:2:2:3};
        \item $1b=2$ (and then $2b=1$) and $xa=y$ (and then $ya=x$) the 3MSA of $\A$ is in Fig. \ref{fig:lemma:3-3:2:2:4}.
      \end{enumerate}
      \begin{figure}[ht]
        \centering
        \subfigure[][$1b=1$ and $xa=x$.]{
        \label{fig:lemma:3-3:2:2:1}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [below of= q_0] {$x$};
            \node[state] (q_3) [right of= q_2] {$1,x$};
            \node[state] (q_4) [below of= q_3,draw=none] {};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node {$b$} (q_2)
                      (q_1) edge [loop above] node {$a$} (q_1)
                      (q_1) edge node {$b$} (q_3)
                      (q_2) edge [loop below] node {$b$} (q_2)
                      (q_2) edge node {$a$} (q_3)
                      (q_3) edge [loop below] node {$a,b$} (q_3)(q_1) edge [loop right,draw=none] node {} (q_1);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}
        }
        \hspace{10pt}
        \subfigure[][$1b=1$, $xa=y$ and $ya=x$.]{
        \label{fig:lemma:3-3:2:2:2}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [below of= q_0] {$x$};
            \node[state] (q_3) [right of= q_2] {$1,x$};
            \node[state] (q_4) [below of=q_3] {$1,y$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node {$b$} (q_2)
                      (q_1) edge [loop above] node {$a$} (q_1)
                      (q_1) edge node {$b$} (q_3)
                      (q_2) edge [loop below] node {$b$} (q_2)
                      (q_2) edge node [swap] {$a$} (q_4)
                      (q_3) edge [loop left] node {$b$} (q_3)
                      (q_3) edge [bend left=10] node {$a$} (q_4)
                      (q_4) edge [bend left=10] node {$a,b$} (q_3)
                      (q_1) edge [loop right,draw=none] node {} (q_1);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}}
        \hspace{10pt}
        \subfigure[][$1b=2$, $2b=1$ and $xa=x$.]{
        \label{fig:lemma:3-3:2:2:3}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [below of= q_0] {$x$};
            \node[state] (q_3) [right of= q_2] {$2,x$};
            \node[state] (q_4) [below of=q_3] {$1,x$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node {$b$} (q_2)
                      (q_1) edge [loop above] node {$a$} (q_1)
                      (q_1) edge node {$b$} (q_3)
                      (q_2) edge [loop below] node {$b$} (q_2)
                      (q_2) edge node [swap] {$a$} (q_4)
                      (q_3) edge [bend right=10] node [swap] {$a,b$} (q_4)
                      (q_4) edge [bend right=10] node [swap] {$b$} (q_3)
                      (q_4) edge [loop left] node {$a$} (q_4)(q_1) edge [loop right,draw=none] node {} (q_1);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}
        }
        \hspace{10pt}
        \subfigure[][$1b=2$, $2b=1$, $xa=y$ and $ya=x$.]{
        \label{fig:lemma:3-3:2:2:4}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [below of= q_0] {$x$};
            \node[state] (q_3) [right of= q_2] {$2,x$};
            \node[state] (q_4) [below of=q_2] {$1,y$};
            \node[state] (q_5) [right of=q_4] {$1,x$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node [swap] {$b$} (q_2)
                      (q_1) edge [loop above] node {$a$} (q_1)
                      (q_1) edge node {$b$} (q_3)
                      (q_2) edge [loop right] node {$b$} (q_2)
                      (q_2) edge node [swap] {$a$} (q_4)
                      (q_3) edge [bend left=10] node {$a$} (q_4)
                      (q_3) edge [bend left=10] node {$b$} (q_5)
                      (q_4) edge [bend left=10] node {$b$} (q_3)
                      (q_4) edge [bend left=10] node {$a$} (q_5)
                      (q_5) edge [bend left=10] node {$a$} (q_4)
                      (q_5) edge [bend left=10] node {$b$} (q_3)(q_1) edge [loop right,draw=none] node {} (q_1);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}}\\
        \caption[]{3MSA for automata that do not satisfy conditions 3. of Lemma \ref{lemma:3-3:2}}
        \label{fig:lemma:3-3:2:2}
      \end{figure}
      In all the subcases, $\A$ is not $3$-compressible.
\end{enumerate}
\end{proof}

\begin{proposition}\label{proposition:3-3}
Let $\A$ be a $(\bf{3},\bf{3})$-automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash x$.
Then $\A$ is proper and $3$-compressible if, and only if, one of the following conditions holds:
\begin{enumerate}
  \item $b=[2,y]\backslash 2$, $y\neq 1$, and either $\{1ba,1b^2a,1b^3a\}\not\subseteq\{2,y\}$ or $Orb_a(1ba)\not\subseteq\{2,y\}$;
  \item $b=[x,1]\backslash x$, $x\neq 2$, and either $\{xba,xb^2a,xb^3a\}\not\subseteq\{1,2\}$ or $Orb_b(xab)\not\subseteq\{1,2\}$;
  \item $b=[x,y]\backslash x$, $x\not\in\{1,2\}$, $y\neq 1$, $1b\in\{1,2\}$, $xa\in\{x,y\}$, and either $Orb_b(1)\not\subseteq\{1,2\}$ or $Orb_a(x)\not\subseteq\{x,y\}$.
\end{enumerate}
Moreover, if $\mathcal{A}$ is proper and $3$-compressible, then one of the words $abab$ or $ab^2ab$ or $ab^3ab$ or $aba^2b$ or $aba^3b$ or $baba$ or $ba^2ba$ or $ba^3ba$ or $bab^2a$ or $bab^3a$ $3$-compresses $\A$.
\end{proposition}

\begin{proof}
If $\A$ is a $3$-compressible $(\bf{3},\bf{3})$-automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash x$, then, from the previous lemmata and corollary, one of the above conditions must hold.

Conversely, we find for any automaton satisfying conditions $1.-3.$ a (short) $3$-compressing word.
\begin{enumerate}
  \item Let $b=[2,y]\backslash 2$, $y\neq 1$,
      \begin{enumerate}
        \item if $\{1ba,1b^2a,1b^3a\}\not\subseteq\{2,y\}$, then either the word $abab$ or $ab^2ab$ or $ab^3ab$ $3$-compresses $\A$, since $\M(aba)=\{1,1ba\}$, $\M(ab^2a)=\{1,1b^2a\}$ and $\M(ab^3a)=\{1,1b^3a\}$;
        \item if $Orb_a(1ba)\not\subseteq\{2,y\}$, then $\{1ba,1ba^2,1ba^3\}\not\subseteq\{2,y\}$ and either the word $abab$ or $aba^2b$ or $aba^3b$ $3$-compresses $\A$, since $\M(aba)=\{1,1ba\}$, $\M(aba^2)=\{1,1ba^2\}$ and $\M(ab^3a)=\{1,1ba^3\}$.
      \end{enumerate}
  \item Let $b=[x,1]\backslash x$, $x\neq 2$, and either $\{xba,xb^2a,xb^3a\}\not\subseteq\{1,2\}$ or $Orb_b(xab)\not\subseteq\{1,2\}$.
      This case reduces to the previous one replacing $a$ with $b$, 1 with 2, 2 with $y$ and $x$ with 1, then either the word $baba$ or $ba^2ba$ or $ba^3ba$ or $bab^2a$ or $bab^3a$ $3$-compresses $\A$.
  \item Let $b=[x,y]\backslash x$, $x\not\in\{1,2\}$, $y\neq 1$, $1b\in\{1,2\}$, $xa\in\{x,y\}$.
      If $Orb_b(1)\not\subseteq\{1,2\}$, then $1b=2$ and $2b\not\in\{1,2\}$, and so the word $ab^2a$ $3$-compresses $\A$, as $\M(ab^2)=\{x,2b\}$; similarly, if $Orb_a(x)\not\subseteq\{x,y\}$,  exchanging $b$ and $a$ and so $x$ with 1 and $y$ with 2, the word $ba^2b$ $3$-compresses $\A$.
\end{enumerate}
\end{proof}

\FloatBarrier

\begin{lemma}\label{lemma:3-4}
Let $\A$ be a $(\bf{3},\bf{4})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash z,\ zb=x$.
If $\A$ is proper then all the following conditions hold:
\begin{enumerate}
  \item $\{1,2\}\cap\{x,z\}\neq \emptyset$,
  \item $z\in\{1,2\}$ or $\{1,za\}\cap\{x,y\}\neq \emptyset$,
  \item $\{1,1b\}\cap\{x,y\}\neq \emptyset$,
  \item $1\in \{x,y\}$ or $\{z,1b\}\cap\{1,2\}\neq \emptyset$.
\end{enumerate}
\end{lemma}

\begin{proof}
If $\{1,2\}\cap\{x,z\}=\emptyset$, then $|\M(b^2a)|=3$; if $z\not\in\{1,2\}$ and $\{1,za\}\cap\{x,y\}=\emptyset$, then $|\M(bab)|=3$; if $\{1,1b\}\cap\{x,y\}=\emptyset$, then $|\M(ab^2)|=3$; if $1\not\in \{x,y\}$ and $\{z,1b\}\cap\{1,2\}=\emptyset$, then $|\M(aba)|=3$.
So each automaton that does not satisfy one of the conditions of the lemma is $3$-compressed by a word of length $3$, and then it is not proper.
\end{proof}

\begin{corollary}\label{corollary:3-4}
Let $\A$ be a \emph{proper} $(\bf{3},\bf{4})$ $3$-compressible automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash z$, $zb=x$.
The following conditions hold:
\begin{enumerate}
  \item $b=[x,y]\backslash 1$, or
  \item $b=[x,y]\backslash 2$ and $\{1,1b\}\cap\{x,y\}\neq\emptyset$, or
  \item $b=[1,y]\backslash z$ or $b=[2,1]\backslash z$ and in both cases $z\neq 2$.
\end{enumerate}
\end{corollary}

\begin{proof}
It is a straightforward consequence of the previous lemma.
\end{proof}

\begin{proposition}\label{proposition:3-4}
Let $\A$ be a $(\bf{3},\bf{4})$-automaton with $a=[1,2]\backslash 1$ and $b=[x,y]\backslash z,\ zb=x$. Then $\A$ is proper and $3$-compressible if, and only if, the following conditions hold:
\begin{enumerate}
  \item if $b=[x,y]\backslash 1$, then $Orb_a(x)\not\subseteq\{x,y\}$,
  \item if $z=2$ and
    \begin{enumerate}
      \item $b=[1,y]\backslash 2$, then $Orb_a(2)\not\subseteq\{2,y\}$ or $2ab\not\in\{1,y\}$,
      \item $b=[x,1]\backslash 2$, then $\{2a,xa\}\neq \{2,x\}$ or $\{2ab,xab\}\neq \{1,x\}$
      \item $b=[x,y]\backslash 2$, $1b=y$, and $1\not\in\{x,y\}$, then $\{xa,ya\}\neq \{x,y\}$,
    \end{enumerate}
  \item if $z\not\in\{1,2\}$ and
    \begin{enumerate}
      \item $b=[1,y]\backslash z$ and $y\neq 2$, then $za\neq z$,
      \item $b=[x,y]\backslash z$ and $\{x,y\}=\{1,2\}$, then $|Orb_a(z)|>2$ or $zab\not\in\{1,2\}$.
   \end{enumerate}
\end{enumerate}
Moreover, if $\mathcal{A}$ is proper and $3$-compressible, then either the word $b^2ab^2$ or $b^2a^2b^2$ or $b^2a^3b^2$ or $b^2abab^2$ $3$-compresses $\A$.
\end{proposition}

\begin{proof}
First observe that from the previous corollary a proper $3$-compressible $(\bf{3},\bf{4})$-automaton always satisfies the antecedent of one of the above conditions, so all the possible cases are taken into account.

\noindent We start proving that a $(\bf{3},\bf{4})$-automaton that does not satisfy the conditions $1.-3.$ is not $3$-compressible.
\begin{enumerate}
  \item Let condition $1.$ be false, \textit{i.e.}, $b=[x,y]\backslash 1$ and $Orb_a(x)\subseteq\{x,y\}$.
      The 3MSA in Fig. \ref{fig:prop:3-4:d:1} proves that $\A$ is not $3$-compressible.
      \begin{figure}[ht]
        \centering
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [right of= q_1] {$1,x$};
            \node[state] (q) [right of= q_2,draw=none] {};
            \node[state] (q_3) [right of= q] {$1,x$};
            \node[state] (q_4) [right of= q_3] {$1,y$};
            \node[state] (q_5) [right of= q_4] {$1,x$};

            \path[->] (q_0) edge node {$a,b$} (q_1)
                      (q_1) edge [loop above] node {$a$} (q_1)
                      (q_1) edge node {$b$} (q_2)
                      (q_2) edge node {$a|xa=x$} (q_3)
                      (q_2) edge [bend right=20] node [swap] {$a|xa=y$} (q_4)
                      (q_2) edge [loop above] node {$b$} (q_2)
                      (q_3) edge [loop above] node {$a,b$} (q_3)
                      (q_4) edge [bend right=20] node [swap] {$a,b$} (q_5)
                      (q_5) edge [bend right=20] node [swap] {$a$} (q_4)
                      (q_5) edge [loop right] node {$b$} (q_5);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}\\
        \caption[]{3MSA for the case in which condition 1. of Proposition \ref{proposition:3-4} is false.}
        \label{fig:prop:3-4:d:1}
      \end{figure}
  \item Let $z=2$.
      \begin{enumerate}
        \item Let condition $2.(a)$ be false, \textit{i.e.}, $b=[1,y]\backslash 2$, $Orb_a(2)\subseteq\{2,y\}$ and $2ab\in\{1,y\}$.
            Observe that if $2a\neq 2$, then $2a=y$ and $ya=2$.
            Since $y\neq 2$, then $yb=2ab\neq 1$, and so  $2ab=y$.
            The 3MSA in Fig. \ref{fig:prop:3-4:d:2:1} proves that $\A$ is not $3$-compressible.
        \item Let condition $2.(b)$ be false, \textit{i.e.}, $b=[x,1]\backslash 2$, $\{2a,xa\}=\{2,x\}$ and $\{2ab,xab\}=\{1,x\}$.
            Observe that if $2a=2$, then $2ab=2b=x$ and so $xab=1$.
            If $xa=2$, then $xab=2b=x$ and so $2ab=1$.
            The 3MSA in Fig. \ref{fig:prop:3-4:d:2:2} proves that $\A$ is not $3$-compressible.
        \item Let condition $2.(c)$ be false, \textit{i.e.}, $b=[x,y]\backslash 2$, $1b=y$, $1\not\in\{x,y\}$ and $\{xa,ya\}= \{x,y\}$.
            The 3MSA in Fig. \ref{fig:prop:3-4:d:2:3} proves that $\A$ is not $3$-compressible.
            \begin{figure}[ht]
                \centering
                \subfigure[][3MSA for the case $b={[1,y]}\backslash 2$, $2b=1$, $Orb_a(2)\subseteq\{2,y\}$ and $2ab\in\{1,y\}$.]{
                \label{fig:prop:3-4:d:2:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_2) [right of= q_0] {$2$};
                    \node[state] (q_1) [right of= q_2] {$1$};
                    \node[state] (q_3) [below of= q_0] {$1,2$};
                    \node[state] (q_9) [right of= q_3] {$2,y$};
                    \node[state] (q_7) [right of= q_9] {$1,y$};
                    \node[state] (q_8) [right of= q_7] {$1,2$};
                    \node[state] (q_4) [below of= q_3] {$1,2$};

                    \path[->] (q_0) edge [bend left=40] node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_2)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge [bend left=20] node {$b$} (q_2)
                              (q_2) edge [bend left=20] node {$a$} (q_1)
                              (q_2) edge node [swap] {$b$} (q_3)
                              (q_3) edge [loop left] node {$b$} (q_3)
                              (q_3) edge node [swap] {$a|2a=2$} (q_4)
                              (q_3) edge [bend left=30] node {$a|2a=y$} (q_7)
                              (q_4) edge [loop below] node {$a,b$} (q_4)
                              (q_7) edge [bend left=10] node {$a$} (q_8)
                              (q_7) edge [bend left=10] node {$b$} (q_9)
                              (q_8) edge [bend left=10] node {$a$} (q_7)
                              (q_8) edge [loop above] node {$b$} (q_8)
                              (q_9) edge [bend right=30] node [swap] {$a,b$} (q_8);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                }
                \hspace{20pt}
                \subfigure[][3MSA for the case $b={[x,1]}\backslash 2$, $2b=x$ $\{2a,xa\}=\{2,x\}$ and $\{2ab,xab\}=\{1,x\}$.]{
                \label{fig:prop:3-4:d:2:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_2) [right of= q_0] {$2$};
                    \node[state] (q_1) [right of= q_2] {$1$};
                    \node[state] (q_3) [below of= q_0] {$2,x$};
                    \node[state] (q_9) [right of= q_3] {$2,x$};
                    \node[state] (q_7) [right of= q_9] {$1,2$};
                    \node[state] (q_8) [right of= q_7] {$1,x$};
                    \node[state] (q_4) [below of= q_3] {$1,x$};
                    \node[state] (q_5) [right of= q_4] {$1,2$};
                    \node[state] (q_6) [right of= q_5] {$2,x$};

                    \path[->] (q_0) edge [bend left=40] node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_2)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge [bend left=20] node {$b$} (q_2)
                              (q_2) edge [bend left=20] node {$a$} (q_1)
                              (q_2) edge node [swap] {$b$} (q_3)
                              (q_3) edge [loop left] node {$b$} (q_3)
                              (q_3) edge node [swap] {$a|2a=2$} (q_4)
                              (q_3) edge [bend left=30] node {$a|2a=x$} (q_7)
                              (q_4) edge [loop below] node {$a$} (q_4)
                              (q_4) edge node {$b$} (q_5)
                              (q_5) edge [loop below] node {$a$} (q_5)
                              (q_5) edge node {$b$} (q_6)
                              (q_6) edge [loop below] node {$b$} (q_6)
                              (q_6) edge [bend right=30] node [swap] {$a$} (q_4)
                              (q_7) edge [bend left=10] node {$a$} (q_8)
                              (q_7) edge [bend left=10] node {$b$} (q_9)
                              (q_8) edge [bend left=10] node {$a,b$} (q_7)
                              (q_9) edge [bend left=10] node {$a$} (q_7)
                              (q_9) edge [loop left] node {$b$} (q_9);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \subfigure[][3MSA for the case $b={[x,y]}\backslash 2$, $2y=x$, $1b=y$, $1\not\in\{x,y\}$ and $\{xa,ya\}=\{x,y\}$.]{
                \label{fig:prop:3-4:d:2:3}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_7) [right of= q_0,draw=none] {};
                    \node[state] (q_1) [above of= q_7] {$1$};
                    \node[state] (q_2) [right of= q_1] {$2,y$};
                    \node[state] (q_3) [right of= q_2,draw=none] {};
                    \node[state] (q_4) [right of= q_3,draw=none] {};
                    \node[state] (q_5) [right of= q_4,draw=none] {};
                    \node[state] (q_6) [right of= q_5] {$1,x$};
                    \node[state] (q_8) [right of= q_7] {$1,y$};
                    \node[state] (q_9) [right of= q_8] {$2,y$};
                    \node[state] (q_10) [right of= q_9] {$1,x$};
                    \node[state] (q_11) [right of= q_10] {$2,x$};
                    \node[state] (q_12) [right of= q_6] {$2,y$};
                    \node[state] (q_14) [below of= q_7] {$2$};
                    \node[state] (q_15) [right of= q_14] {$2,x$};
                    \node[state] (q_16) [right of= q_15,draw=none] {};
                    \node[state] (q_17) [right of= q_16,draw=none] {};
                    \node[state] (q_18) [right of= q_17,draw=none] {};
                    \node[state] (q_19) [right of= q_18] {$1,y$};
                    \node[state] (q_13) [right of= q_19] {$2,x$};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_0) edge node {$b$} (q_14)
                              (q_1) edge [loop above] node {$a$} (q_1)
                              (q_1) edge node {$b$} (q_2)
                              (q_2) edge node {$a|xa=x$} (q_8)
                              (q_2) edge node {$a|xa=y$} (q_6)
                              (q_2) edge [bend right=30] node [swap] {$b$} (q_15)
                              (q_6) edge [bend right=10] node [swap] {$a$} (q_19)
                              (q_6) edge [bend right=20] node [swap] {$b$} (q_12)
                              (q_8) edge [loop below] node {$a$} (q_8)
                              (q_8) edge [bend right=20] node [swap] {$b$} (q_9)
                              (q_9) edge [bend right=20] node [swap] {$a$} (q_8)
                              (q_9) edge [bend left=30] node {$b$} (q_11)
                              (q_10) edge node {$b$} (q_9)
                              (q_10) edge [loop below] node {$a$} (q_10)
                              (q_11) edge node {$a$} (q_10)
                              (q_11) edge [loop below] node {$b$} (q_11)
                              (q_12) edge node {$b$} (q_13)
                              (q_12) edge [bend right=20] node [swap] {$a$} (q_6)
                              (q_13) edge node {$a$} (q_19)
                              (q_13) edge [loop below] node {$b$} (q_13)
                              (q_14) edge node {$a$} (q_1)
                              (q_14) edge node {$b$} (q_15)
                              (q_15) edge node [swap] {$a|xa=y$} (q_19)
                              (q_15) edge node [swap] {$a|xa=x$} (q_10)
                          (q_15) edge [loop below] node {$b$} (q_15)
                          (q_19) edge node [swap] {$b$} (q_12)
                          (q_19) edge [bend right=10] node [swap] {$a$} (q_6);

                \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}\\
                \caption[]{3MSA for the case in which condition 2. of Proposition \ref{proposition:3-4} is false.}
                \label{fig:prop:3-4:d:2}
            \end{figure}
            \FloatBarrier
    \end{enumerate}
  \item Let $z\not\in\{1,2\}$.
    \begin{enumerate}
      \item Let condition $3.(a)$ be false, \textit{i.e.}, $b=[1,y]\backslash z$, $y\neq 2$ but $za=z$.
          Then for all $w\in a^*b$ and $u\in\{a,b\}^+$, $\M(w)=\{z\}$ and $\M(wu)=\{1,z\}$, so $\A$ is not $3$-compressible.
      \item Let condition $3.(b)$ be false, \textit{i.e.}, $b=[x,y]\backslash z$ and $\{x,y\}=\{1,2\}$, but $|Orb_a(z)|\leq2$ and $zab\in\{1,2\}$.
          If $x=1$ and $y=2$, then the 3MSA in Fig. \ref{fig:prop:3-4:d:3:2} proves that $\A$ is not $3$-compressible. Else, if $x=2$ and $y=1$, then the 3MSA in Fig. \ref{fig:prop:3-4:d:3:3} proves that $\A$ is not $3$-compressible.
          \begin{figure}[ht]
              \centering
              \subfigure[][3MSA for the case $b={[1,2]}\backslash z$, $|Orb_a(z)|\leq2$ and $zab\in\{1,2\}$.]{
              \label{fig:prop:3-4:d:3:2}
              {\footnotesize
              \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                  \node[state] (q_0) {};
                  \node[state] (q_1) [right of= q_0] {$z$};
                  \node[state] (q_2) [right of= q_1] {$1$};
                  \node[state] (q_3) [right of= q_2] {$1,z$};
                  \node[state] (qq) [draw=none,right of= q_3] {};
                  \node[state] (q_4) [below of= q_0] {$1,za$};
                  \node[state] (q_5) [right of=q_4,draw=none] {};
                  \node[state] (q_6) [right of= q_5] {$1,z$};
                  \node[state] (q_7) [right of= q_6] {$1,za$};
                  \node[state] (q_8) [below of= q_4] {$2,z$};
                  \node[state] (q_9) [right of= q_8] {$1,za$};
                  \node[state] (q_10) [right of= q_9] {$1,z$};

                  \path[->] (q_0) edge [bend left=40] node {$a$} (q_2)
                            (q_0) edge node {$b$} (q_1)
                            (q_1) edge [bend right=30] node [swap] {$a|za=2,b$} (q_3)
                            (q_1) edge node [swap] {$a|za\neq z$} (q_4)
                            (q_2) edge [loop above] node {$a$} (q_2)
                            (q_2) edge node [swap] {$b$} (q_1)
                            (q_3) edge [loop above] node {$a,b$} (q_3)
                            (q_4) edge node {$b|zab=1,a$} (q_6)
                            (q_4) edge node {$b|zab=2$} (q_8)
                            (q_6) edge [loop below] node {$b$} (q_6)
                            (q_6) edge [bend left=10] node {$a$} (q_7)
                            (q_7) edge [bend left=10] node {$a,b$} (q_6)
                            (q_8) edge [bend left=10] node {$a$} (q_9)
                            (q_8) edge [bend right=40] node [swap] {$b$} (q_10)
                            (q_9) edge [bend left=10] node {$b$} (q_8)
                            (q_9) edge [bend left=10] node {$a$} (q_10)
                            (q_10) edge [bend left=10] node {$a$} (q_9)
                            (q_10) edge [loop right] node {$b$} (q_10);

                  \draw [->] (-.5,.5) -- (-.27,.27);

              \end{tikzpicture}}
              }
              \hspace{20pt}
              \subfigure[][3MSA for the case $b={[2,1]}\backslash z$, $|Orb_a(z)|\leq 2$ and $zab\in\{1,2\}$.]{
              \label{fig:prop:3-4:d:3:3}
              {\footnotesize
              \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                  \node[state] (q_1) [draw=none] {};
                  \node[state] (q_0) [right of= q_1] {};
                  \node[state] (q_2) [right of= q_0] {$z$};
                  \node[state] (q_11) [right of=q_2] {$1$};
                  \node[state] (q_3) [below of= q_0] {$1,za$};
                  \node[state] (q_4) [right of= q_3,draw=none] {};
                  \node[state] (q_5) [right of= q_4] {$1,z$};
                  \node[state] (q_6) [left of= q_3] {$1,z$};
                  \node[state] (q_7) [below of= q_6] {$2,z$};
                  \node[state] (q_8) [below of= q_4] {$2,z$};
                  \node[state] (q_9) [right of= q_5] {$2,z$};

                  \path[->] (q_0) edge node {$b$} (q_2)
                            (q_0) edge [bend left=40] node {$a$} (q_11)
                            (q_11) edge [loop above] node {$a$} (q_11)
                            (q_11) edge node [swap] {$b$} (q_2)
                            (q_2) edge node {$b$} (q_8)
                            (q_2) edge node {$a|za=z$} (q_5)
                            (q_2) edge node [swap] {$a|za\neq z$} (q_3)
                        (q_3) edge [bend left=10] node {$a,b$} (q_6)
                        (q_5) edge [loop left] node {$a$} (q_5)
                    (q_5) edge [bend left=10] node {$b$} (q_9)
                    (q_6) edge [bend left=10] node {$a$} (q_3)
                    (q_6) edge node [swap] {$b$} (q_7)
                    (q_7) edge node {$a$} (q_3)
                    (q_7) edge [loop below] node {$b$} (q_7)
                    (q_8) edge [loop below] node {$b$} (q_8)
                    (q_8) edge node [swap] {$a|za=z$} (q_5)
                    (q_8) edge node {$a|za\neq z$} (q_3)
                    (q_9) edge [bend left=10] node {$a$} (q_5)
                    (q_9) edge [loop below] node {$b$} (q_9);

              \draw [->] (.9,.5) -- (1.13,.27);

              \end{tikzpicture}}}\\
              \caption[]{3MSA for the case in which condition 3.(b) of Proposition \ref{proposition:3-4} is false.}
          \end{figure}
    \end{enumerate}
\end{enumerate}

\FloatBarrier

Conversely, we find for any automaton satisfying conditions $1.-3.$ a (short) $3$-compressing word.
\begin{enumerate}
  \item Let $b=[x,y]\backslash 1$ and $Orb_a(x)\not\subseteq \{x,y\}$, whence $xa\neq x$.
      Then either $xa$ or $xa^2$ are different from $y$, and so either the word $b^2ab$ or $b^2a^2b$ $3$-compresses $\A$.
  \item Let $z=2$, we consider various subcases.
      \begin{enumerate}
        \item Let $b=[1,y]\backslash 2$.
            Then $2a\neq 2$, otherwise $Orb_a(2)=\{2\}$ and $2ab=1$, against the hypothesis.
            Hence $2ab=y$ and $2a^2b\neq y$.
            The P3MSA in Fig. \ref{fig:prop:3-4:r:2:1} proves that either the word $b^2ab^2$ or $b^2a^2b^2$ $3$-compresses $\A$;
            \begin{figure}[ht]
                \centering
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_1] {$1,2$};
                    \node[state] (q_3) [right of= q_2] {$1,2a$};
                    \node[state] (q_4) [right of= q_3,draw=none] {};
                    \node[state] (q_5) [right of= q_4] {$2,2ab$};
                    \node[state,accepting] (q_8) [right of= q_5] {};
                    \node[state] (q_7) [right of= q_8] {$2,2a^2b$};
                    \node[state] (q_6) [right of= q_7] {$1,2a^2$};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_1) edge node {$b$} (q_2)
                              (q_2) edge node {$a$} (q_3)
                              (q_3) edge node {$b|2ab\neq y$} (q_5)
                              (q_5) edge node {$b$} (q_8)
                              (q_3) edge [bend right=25] node [swap] {$a|2ab=y$} (q_6)
                              (q_6) edge node [swap] {$b$} (q_7)
                              (q_7) edge node [swap] {$b$} (q_8);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}
                \caption[]{P3MSA for the case 2.(a) of Proposition \ref{proposition:3-4}.}
                \label{fig:prop:3-4:r:2:1}
            \end{figure}
        \item Let $b=[x,1]\backslash 2$:
            \begin{enumerate}
              \item if $\{2ab,xab\}\neq\{1,x\}$, then the P3MSA in Fig. \ref{fig:prop:3-4:r:2:2:1} proves that the word $b^2ab^2$ or $b^2a^2b^2$ or $b^2abab^2$ $3$-compresses $\A$.
                  Observe that if $xab=x$, then $xa=2$ and $2ab\not\in\{1,x\}$.
                  \begin{figure}[ht]
                    \centering
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=4.8em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$2$};
                        \node[state] (q_2) [right of= q_1] {$2,x$};
                        \node[state] (q_3) [right of= q_2] {$1,xa$};
                        \node[state] (q_4) [right of= q_3,draw=none] {};
                        \node[state] (q_5) [right of= q_4] {$1,2$};
                        \node[state] (q_6) [right of= q_5] {$1,2a$};
                        \node[state] (q_7) [right of= q_6] {$2,2ab$};
                        \node[state] (q_8) [below of= q_4] {$1,2a$};
                        \node[state] (q_9) [right of= q_8] {$2,2ab$};
                        \node[state] (q_10) [right of= q_9] {$2,xab$};
                        \node[state,accepting] (q_11) [right of= q_10] {};

                        \path[->] (q_0) edge node {$b$} (q_1)
                                  (q_1) edge node {$b$} (q_2)
                                  (q_2) edge node {$a$} (q_3)
                                  (q_3) edge node {$b|xab=1$} (q_5)
                                  (q_3) edge node {$b|xab\not\in\{1,x\}$} (q_10)
                                  (q_3) edge node [swap] {$a|xab=x$} (q_8)
                                  (q_5) edge node {$a$} (q_6)
                                  (q_6) edge node {$b$} (q_7)
                                  (q_7) edge node {$b$} (q_11)
                                  (q_10) edge node {$b$} (q_11)
                                  (q_8) edge node {$b$} (q_9)
                                  (q_9) edge [bend right=28] node [swap] {$b$} (q_11);

                        \draw [->] (-.5,.5) -- (-.27,.27);

                    \end{tikzpicture}}\\
                    \caption[]{P3MSA for the case $b={[x,1]}\backslash 2$ and $\{2ab,xab\}\neq\{1,x\}$.}
                    \label{fig:prop:3-4:r:2:2:1}
                \end{figure}
              \item if $2ab=x$, $xab=1$, and $\{2a,xa\}\neq\{2,x\}$, then $2ab=2b$, $2a=2$ and then $xa\not\in\{2,x\}$. So $\M(b^2a)=\{1,xa\}$, $\M(b^2a^2)=\{1,xa^2\}$ and $\M(b^2a^2b)=\{2,xa^2b\}$. If $xa^2b=x=2b$, then $xa^2=2a$, and so $xa=2$, against the hypothesis. Else, if $xa^2b=1=xab$, then $xa^2=xa$, and so $xa=x$, against the hypothesis. Then it follows that $|\M(b^2a^2b^2)|=3$ and the word $b^2a^2b^2$ $3$-compresses $\A$.
              \item if $2ab=1$, $xab=x$, and $\{2a,xa\}\neq\{2,x\}$, then $xab=2b$, $xa=2$ and then $2a\not\in\{2,x\}$.
                  Then the P3MSA in Fig. \ref{fig:prop:3-4:r:2:2} proves that any word belonging to the language $\mathcal{L}=b(a^+b)^*(ba)^+a(ba)^*ab(b+ab^2)$ (and in particular $b^2a^3b^2$) $3$-compresses $\A$.
                  Indeed, if $2a^2b=x=2b$, then $2a^2=2$, against the hypothesis, else, if $2a^2b=1=2ab$, then $2a^2=2a$, and so $2a=2$, against the hypothesis, and so $2a^2b\not\in\{1,x\}$. Moreover, if $2a^2bab=1=2ab$, then $2a^2ba=2a$, and so $2a^2b=2$, against the hypothesis else, if $2a^2bab=x=xab$, then $xa^2ba=xa$, and so $2a^2b=x$, against the hypothesis, and so $2a^2bab\not\in\{1,x\}$.
                  \begin{figure}[ht]
                    \centering
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=4.8em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$2$};
                        \node[state] (q_2) [right of= q_1] {$2,x$};
                        \node[state] (q_3) [right of= q_2] {$1,2$};
                        \node[state] (q_4) [right of= q_3] {$1,2a$};
                        \node[state] (q_5) [right of= q_4] {$1,2a^2$};
                        \node[state,inner sep=-4pt] (q_6) [right of= q_5] {{\scriptsize $\begin{array}{c}2, \\2,2a^2b\end{array}$}};
                        \node[state,accepting] (q_7) [below of= q_6] {};
                        \node[state,inner sep=-4pt] (q_8) [right of= q_6] {{\scriptsize $\begin{array}{c}1, \\2a^2ba\end{array}$}};
                        \node[state,inner sep=-4pt] (q_9) [below of= q_8] {{\scriptsize $\begin{array}{c}2, \\2a^2bab\end{array}$}};
                        \node[state] (q_10) [below of= q_1] {$1$};

                        \path[->] (q_0) edge node {$b$} (q_1)
                                  (q_1) edge node {$b$} (q_2)
                                  (q_2) edge [loop below] node {$b$} (q_2)
                                  (q_2) edge [bend left=10] node {$a$} (q_3)
                                  (q_3) edge [bend left=10] node {$b$} (q_2)
                                  (q_3) edge [bend left=10] node {$a$} (q_4)
                                  (q_4) edge [bend left=10] node {$b$} (q_3)
                                  (q_4) edge node {$a$} (q_5)
                                  (q_5) edge node {$b$} (q_6)
                                  (q_6) edge node {$b$} (q_7)
                                  (q_6) edge node {$a$} (q_8)
                                  (q_8) edge node {$b$} (q_9)
                                  (q_9) edge node [swap] {$b$} (q_7)
                                  (q_1) edge [bend left=10] node {$a$} (q_10)
                                  (q_10) edge [bend left=10] node {$b$} (q_1)
                                  (q_10) edge [loop left] node {$a$} (q_10);

                        \draw [->] (-.5,.5) -- (-.27,.27);

                    \end{tikzpicture}}\\
                    \caption[]{P3MSA for the case $b={[x,1]}\backslash 2$, $2ab=1$, $xab=x$ and $\{2a,xa\}\neq\{2,x\}$.}
                    \label{fig:prop:3-4:r:2:2}
                \end{figure}
            \end{enumerate}

        \item Let $b=[x,y]\backslash 2$, $1b=y$, $1\not\in\{x,y\}$ and $\{xa,ya\}\neq \{x,y\}$.
            Observe that if $xa\in\{x,y\}$, then $ya\not\in \{x,y\}$.
            The P3MSA in Fig. \ref{fig:prop:3-4:r:2:3} proves that in this case either the word $b^2ab$ or $b^2abab$ $3$-compresses $\A$.
            \begin{figure}[ht]
            \centering
            {\footnotesize
            \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                \node[state] (q_0) {};
                \node[state] (q_1) [right of= q_0] {$2$};
                \node[state] (q_2) [right of= q_1] {$2,x$};
                \node[state] (q_3) [right of= q_2] {$1,xa$};
                \node[state] (q_4) [right of= q_3,draw=none] {};
                \node[state,accepting] (q_5) [right of= q_4] {};
                \node[state] (q_6) [right of= q_5] {$1,ya$};
                \node[state] (q_7) [right of= q_6] {$2,y$};

                \path[->] (q_0) edge node {$b$} (q_1)
                          (q_1) edge node {$b$} (q_2)
                          (q_2) edge node {$a$} (q_3)
                          (q_3) edge node {$b|xa\not\in\{x,y\}$} (q_5)
                          (q_3) edge [bend right=18] node [swap] {$b|xa\in\{x,y\}$} (q_7)
                          (q_7) edge node [swap] {$a$} (q_6)
                          (q_6) edge node [swap] {$b$} (q_5);

                \draw [->] (-.5,.5) -- (-.27,.27);

            \end{tikzpicture}}\\
            \caption[]{P3MSA for the case $b=[x,y]\backslash 2$, $1b=y$, $1\not\in\{x,y\}$ and $\{xa,ya\}\neq \{x,y\}$.}
            \label{fig:prop:3-4:r:2:3}
            \end{figure}
    \end{enumerate}
  \item Let $z\not\in\{1,2\}$, we consider two main subcases.
    \begin{enumerate}
      \item Let $b=[1,y]\backslash z$, $y\neq 2$ and $za\neq z$. Then $\M(ba)=\{1,za\}$, $\M(bab)=\{z,zab\}$.
          If $zab\neq y$, then $|\M(bab^2)|=3$, else if $zab=y$ then $|\M(baba)|=3$, hence either the word $bab^2$ or $baba$ $3$-compresses $\A$.
      \item Let $\{x,y\}=\{1,2\}$. We consider two subcases.
        \begin{enumerate}
          \item Let $b=[x,y]\backslash z$ and $|Orb_a(z)|>2$.
            In particular $za\neq z$, $zab\neq za^2b$ and $z\neq za^2$.
            If $zab=y$, then $za^2b\not\in\{zb,zab\}=\{1,2\}$. The P3MSA in Fig. \ref{fig:prop:3-4:r:3:2} proves that either the word $ba^2b^2$ or $bab^2$ $3$-compresses $\A$.
            \begin{figure}[ht]
            \centering
            {\footnotesize
            \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                \node[state] (q_0) {};
                \node[state] (q_1) [right of= q_0] {$z$};
                \node[state] (q_2) [right of= q_1] {$1,za$};
                \node[state] (q_3) [right of= q_2,draw=none] {};
                \node[state] (q_4) [right of= q_3] {$z,zab$};
                \node[state,accepting] (q_7) [right of= q_4] {};
                \node[state] (q_6) [right of= q_7] {$z,za^2b$};
                \node[state] (q_5) [right of= q_6] {$1,za^2$};

                \path[->] (q_0) edge node {$b$} (q_1)
                          (q_1) edge node {$a$} (q_2)
                          (q_2) edge node {$b|zab\neq y$} (q_4)
                          (q_2) edge [bend right=22] node [swap] {$a|zab=y$} (q_5)
                          (q_5) edge node [swap] {$b$} (q_6)
                          (q_6) edge node [swap] {$b$} (q_7)
                          (q_4) edge node {$b$} (q_7);

                \draw [->] (-.5,.5) -- (-.27,.27);

            \end{tikzpicture}}\\
            \caption[]{P3MSA for the case $b={[x,y]}\backslash z$, $\{x,y\}=\{1,2\}$ and $|Orb_a(z)|>2$.}
            \label{fig:prop:3-4:r:3:2}
            \end{figure}
          \item Let $b=[x,y]\backslash z$ and $zab\not\in\{1,2\}$.
            Then $\M(bab)=\{z,zab\}$ and $|\M(bab^2)|=|\M(baba)|=3$, both the words $bab^2$ and $baba$ $3$-compress $\A$.
        \end{enumerate}
    \end{enumerate}
\end{enumerate}
\end{proof}

\FloatBarrier

\begin{lemma}\label{lemma:4-4}
Let $\A$ be a $(\bf{4},\bf{4})$ $3$-compressible automaton with $a=[1,2]\backslash 3$, $3a=1$ and $b=[x,y]\backslash z$, $zb=x$.
If $\A$ is proper then all the following conditions hold:
\begin{enumerate}
  \item $\{1,2\}\cap\{x,z\}\neq \emptyset$,
  \item $z\in\{1,2\}$ or $\{3,za\}\cap\{x,y\}\neq \emptyset$,
  \item $\{3,3b\}\cap\{x,y\}\neq \emptyset$,
  \item $\{1,3\}\cap\{x,y\}\neq \emptyset$,
  \item $3\in \{x,y\}$ or $\{z,3b\}\cap\{1,2\}\neq \emptyset$,
  \item $\{z,za\}\cap\{1,2\}\neq \emptyset$.
\end{enumerate}
\end{lemma}

\begin{proof}
If $\{1,2\}\cap\{x,z\}=\emptyset$, then $\M(b^2)=\{x,z\}$ and $|\M(b^2a)|=3$;
if $z\not\in\{1,2\}$ and $\{3,za\}\cap\{x,y\}=\emptyset$, then $\M(ba)=\{3,za\}$ and $|\M(bab)|=3$;
if $\{3,3b\}\cap\{x,y\}=\emptyset$, then $\M(ab)=\{3,zb\}$ and $|\M(ab^2)|=3$;
if $\{1,3\}\cap\{x,y\}=\emptyset$, then $\M(a^2)=\{1,3\}$ and $|\M(a^2b)|=3$;
if $3\not\in \{x,y\}$ and $\{z,3b\}\cap\{1,2\}=\emptyset$, then $\M(ab)=\{z,3b\}$ and $|\M(a^2b)|=3$;
if $\{z,za\}\cap\{1,2\}=\emptyset$, then $\M(ba)=\{z,3b\}$ and $|\M(bab)|=3$.
Then each automaton that does not satisfies one of the above is not proper.
\end{proof}

\begin{corollary}\label{corollary:4-4}
Let $\A$ be a \emph{proper} $(\bf{4},\bf{4})$ $3$-compressible automaton with $a=[1,2]\backslash 3,\ 3a=1$ and $b=[x,y]\backslash z,\ zb=x$.
The following conditions hold:
\begin{enumerate}
  \item if $z=1$, then $3\in \{x,y\}$,
  \item if $z=2$, then $3\in \{x,y\}$ or it is $1\in \{x,y\}$ and $3b\in\{x,y\}$,
  \item if $z\not\in\{1,2\}$, then $x\in \{1,2\}$ and $za\in\{1,2\}$.
\end{enumerate}
\end{corollary}

\begin{proof}
It is a straightforward consequence of the previous lemma.
Observe that not all the conditions of Lemma \ref{lemma:4-4} are applied, so some automaton satisfying the conditions of the corollary could possibly be not proper or not $3$-compressible.
\end{proof}

\begin{proposition}\label{proposition:4-4}
Let $\A$ be a $(\bf{4},\bf{4})$-automaton with $a=[1,2]\backslash 3,\ 3a=1$ and $b=[x,y]\backslash z,\ zb=x$.
Then $\A$ is proper and $3$-compressible if, and only if, the following conditions hold:
\begin{enumerate}
  \item if $z=1$, then $y=3$ and it is $xa\neq 2$ or $2b \neq 3$,
  \item if $z=2$ and $3\not\in\{x,y\}$, then $1\in\{x,y\}$ and $3b \in\{x,y\}$,
  \item if $z=2$ and $3\in\{x,y\}$, if $q\in\{x,y\}\setminus\{3\}$ then $qa\neq 2$ or $1b \neq y$,
  \item if $b=[x,y]\backslash z$, $z\not\in\{1,2\}$, $x\in\{1,2\}$ and $za\in\{1,2\}$, then $y=3$.
\end{enumerate}
Moreover, if $\mathcal{A}$ is proper and $3$-compressible, then either the word $b^2a^2$ or $b^2ab^2$ or $a^2b^2$ or $a^2ba^2$ $3$-compresses $\A$.
\end{proposition}

\begin{proof}
First observe that from Corollary \ref{corollary:4-4}, a proper $3$-compressible $(\bf{4},\bf{4})$-automaton always satisfies the antecedent of one of the above conditions, so all the possible cases are taken into account.

\noindent We start proving that a $(\bf{4},\bf{4})$-automaton that does not satisfy conditions 1.-4. is not proper or it is not $3$-compressible.
\begin{enumerate}
  \item Let condition 1. be false, \textit{i.e.}, $b=[x,y]\backslash 1$ but either $y\neq 3$ or $xa=2$ and $2b=3$.
      Observe that if $y\neq 3$ then from the previous corollary we have $x=3$.
      The 3MSA in Fig. \ref{fig:prop:4-4:d:1} proves that if condition 1. is false, then $\A$ is not $3$-compressible.
      \begin{figure}[ht]
        \centering
        \subfigure[][Case $y\neq 3$ and $x=3$.]{
        \label{fig:prop:4-4:d:1:1}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$3$};
            \node[state] (q_2) [right of= q_1] {$1,3$};
            \node[state] (q_3) [below of= q_1] {$1$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node [swap] {$b$} (q_3)
                      (q_1) edge [bend left=10] node {$b$} (q_3)
                      (q_1) edge node {$a$} (q_2)
                      (q_2) edge [loop right] node {$a,b$} (q_2)
                      (q_3) edge [bend left=10] node {$a$} (q_1)
                      (q_3) edge [draw=none,loop below] node {\phantom{b}} (q_3)
                      (q_3) edge node [swap] {$b$} (q_2);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}
        }
        \hspace{20pt}
        \subfigure[][Case $xa=2$ and $2b=3$.]{
        \label{fig:prop:4-4:d:1:2}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$3$};
            \node[state] (q_2) [right of= q_1] {$1,3$};
            \node[state] (q_3) [below of= q_0] {$1$};
            \node[state] (q_4) [right of= q_3] {$x,1$};
            \node[state] (q_5) [right of= q_4] {$2,3$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node [swap] {$b$} (q_3)
                      (q_1) edge [bend left=10] node {$b$} (q_3)
                      (q_1) edge node {$a$} (q_2)
                      (q_2) edge [loop right] node {$a$} (q_2)
                      (q_2) edge node {$b$} (q_4)
                      (q_3) edge [bend left=10] node {$a$} (q_1)
                      (q_3) edge node [swap] {$b$} (q_4)
                      (q_4) edge [loop below] node {$b$} (q_4)
                      (q_4) edge node [swap] {$a$} (q_5)
                      (q_5) edge node [swap] {$a,b$} (q_2);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}}\\
        \caption[]{3MSA for the case in which condition 1. of Proposition \ref{proposition:4-4} is false.}
        \label{fig:prop:4-4:d:1}
      \end{figure}
  \item Let condition 2. be false, \textit{i.e.}, $b=[x,y]\backslash 2$ and $3\not\in\{x,y\}$ but either $1\not\in\{x,y\}$ or $3b\not\in\{x,y\}$.
      From conditions 3. and 4. of Lemma \ref{lemma:4-4} we have that in this cases $\A$ is not proper, as it is $3$-compressed either by $ab^2$ or by $a^2b$.
  \item Let condition 3. be false. If $b=[x,3]\backslash 2$ but $xa=2$ and $1b=3$, then the 3MSA in Fig. \ref{fig:prop:4-4:d:2:1} proves that  $\A$ is not $3$-compressible.
      Else, if $b=[3,y]\backslash 2$ but $ya=2$ and $1b=y$, then the 3MSA in Fig. \ref{fig:prop:4-4:d:2:2} proves $\A$ is not $3$-compressible.
      \begin{figure}[ht]
        \centering
        \subfigure[][$b={[x,3]}\backslash 2$, $xa=2$ and $1b=3$.]{
        \label{fig:prop:4-4:d:2:1}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$3$};
            \node[state] (q_2) [right of= q_1] {$1,3$};
            \node[state] (q_3) [below of= q_0] {$2$};
            \node[state] (q_4) [right of= q_3] {$x,2$};
            \node[state] (q_5) [right of= q_4] {$2,3$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node [swap] {$b$} (q_3)
                      (q_1) edge [bend left=10] node {$b$} (q_3)
                      (q_1) edge node {$a$} (q_2)
                      (q_2) edge [loop right] node {$a\phantom{,b}$} (q_2)
                      (q_2) edge [bend left=10]node {$b$} (q_5)
                      (q_3) edge [bend left=10] node {$a$} (q_1)
                      (q_3) edge node [swap] {$b$} (q_4)
                      (q_4) edge [loop below] node {$b$} (q_4)
                      (q_4) edge [bend left=10] node {$a$} (q_5)
                      (q_5) edge [bend left=10] node {$b$} (q_4)
                      (q_5) edge [bend left=10] node {$a$} (q_2);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}
        }
        \hspace{20pt}
        \subfigure[][$b={[3,y]}\backslash 2$, $ya=2$ and $1b=y$.]{
        \label{fig:prop:4-4:d:2:2}
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$3$};
            \node[state] (q_2) [right of= q_1] {$1,3$};
            \node[state] (q_3) [below of= q_0] {$2$};
            \node[state] (q_4) [right of= q_3] {$2,3$};
            \node[state] (q_5) [right of= q_4] {$2,y$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_0) edge node [swap] {$b$} (q_3)
                      (q_1) edge [bend left=10] node {$b$} (q_3)
                      (q_1) edge node {$a$} (q_2)
                      (q_2) edge [loop right] node {$a$} (q_2)
                      (q_2) edge node {$b$} (q_5)
                      (q_3) edge [bend left=10] node {$a$} (q_1)
                      (q_3) edge node [swap] {$b$} (q_4)
                      (q_4) edge [loop below] node {$b$} (q_4)
                      (q_4) edge node [swap] {$a$} (q_2)
                      (q_5) edge node [swap] {$a,b$} (q_4);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}}\\
        \caption[]{3MSA for the case in which condition 3. of Proposition \ref{proposition:4-4} is false.}
        \label{fig:prop:4-4:d:2}
      \end{figure}
  \item Let condition 4. be false, \textit{i.e.}, $b=[x,y]\backslash z$, $z\not\in\{1,2\}$, $x\in\{1,2\}$ and $za\in\{1,2\}$, but $y\neq 3$.
      We have to consider the following subcases.
      \begin{enumerate}
        \item Let $za=1$, hence $z=3$ and $zb=x$.
            If $x=1$, then for all $w\in\{a,b\}^+$ with $|w|\geq 2$, we have $\M(w)=\{1,3\}$, and then $\A$ is not $3$-compressible.
            If $x=2$, then by condition 4 of Lemma \ref{lemma:4-4} we have $y=1$, and for all $w\in\{a,b\}^+$ we have $M(wa)=\{1,3\}$ and $\M(wb)=\{2,3\}$ and again $\A$ is not $3$-compressible.
        \item Let $za=2$, hence $z\neq 3$.
            We consider two further subcases:
            \begin{enumerate}
              \item if $x=1$, then $3b\neq 1$ and by condition 2. of Lemma \ref{lemma:4-4} $za=y=2$, and by condition 3. of Lemma \ref{lemma:4-4} we have $3b=2$.
                  The 3MSA in Fig. \ref{fig:prop:4-4:d:5:1} proves that $\A$ is not $3$-compressible;
              \item if $x=2$, then by condition 4. of Lemma \ref{lemma:4-4} we have $y=1$ and by condition 3. of Lemma \ref{lemma:4-4} we have $3b=1$.
                  The 3MSA in Fig. \ref{fig:prop:4-4:d:5:2} proves that $\A$ is not $3$-compressible.
                  \begin{figure}[ht]
                    \centering
                    \subfigure[][Case $x=1$.]{
                    \label{fig:prop:4-4:d:5:1}
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$3$};
                        \node[state] (q_2) [right of= q_1] {$1,3$};
                        \node[state] (q_3) [right of= q_2] {$2,z$};
                        \node[state] (q_4) [below of= q_1] {$z$};
                        \node[state] (q_5) [right of= q_4] {$2,3$};
                        \node[state] (q_6) [right of= q_5] {$1,z$};

                        \path[->] (q_0) edge node {$a$} (q_1)
                                  (q_0) edge node {$b$} (q_4)
                                  (q_1) edge node {$a$} (q_2)
                                  (q_1) edge [bend left=30] node {$b$} (q_3)
                                  (q_2) edge [max distance=5mm,in=215,out=245,loop] node {$a$} (q_2)
                                  (q_2) edge node {$b$} (q_3)
                                  (q_3) edge [bend left=10] node {$a$} (q_5)
                                  (q_3) edge [bend left=10] node {$b$} (q_6)
                                  (q_4) edge node {$a$} (q_5)
                                  (q_4) edge [bend right=30] node [swap] {$b$} (q_6)
                                  (q_5) edge node {$a$} (q_2)
                                  (q_5) edge [bend left=10] node {$b$} (q_3)
                                  (q_6) edge node {$a$} (q_5)
                                  (q_6) edge [bend left=10] node {$b$} (q_3)
                                  (q_6) edge [loop right,draw=none] node {} (q_6);

                        \draw [->] (-.5,.5) -- (-.27,.27);

                    \end{tikzpicture}}
                    }
                    \hspace{20pt}
                    \subfigure[][Case $x=2$.]{
                    \label{fig:prop:4-4:d:5:2}
                    {\footnotesize
                    \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

                        \node[state] (q_0) {};
                        \node[state] (q_1) [right of= q_0] {$3$};
                        \node[state] (q_2) [right of= q_1] {$1,3$};
                        \node[state] (q_3) [right of= q_2] {$1,z$};
                        \node[state] (q_4) [below of= q_1] {$z$};
                        \node[state] (q_5) [right of= q_4] {$2,3$};
                        \node[state] (q_6) [right of= q_5] {$2,z$};

                        \path[->] (q_0) edge node {$a$} (q_1)
                                  (q_0) edge node {$b$} (q_4)
                                  (q_1) edge node {$a$} (q_2)
                                  (q_1) edge [bend left=30] node {$b$} (q_3)
                                  (q_2) edge [max distance=5mm,in=215,out=245,loop] node {$a$} (q_2)
                                  (q_2) edge node {$b$} (q_3)
                                  (q_3) edge [bend left=10] node {$a$} (q_5)
                                  (q_3) edge node {$b$} (q_6)
                                  (q_4) edge node {$a$} (q_5)
                          (q_4) edge [bend right=30] node [swap] {$b$} (q_6)
                          (q_5) edge node {$a$} (q_2)
                          (q_5) edge [bend left=10] node {$b$} (q_3)
                          (q_6) edge node {$a$} (q_5)
                          (q_6) edge [loop right] node {$b$} (q_3);

                \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \caption[]{3MSA for the case in which condition 4. of Proposition \ref{proposition:4-4} is false and $za=2$.}
                \label{fig:prop:4-4:d:5}
                \end{figure}
            \end{enumerate}
      \end{enumerate}
\end{enumerate}

Conversely, we find for each automaton satisfying conditions 1.-4. a (short) $3$-compressing word.
\begin{enumerate}
  \item Let $b=[x,3]\backslash 1$ and $xa\neq 2$ or $2b\neq 3$.
      Observe that $xa\neq 1$, as $3a=1$ and $x\neq 3$.
      The P3MSA in Fig. \ref{fig:prop:4-4:r:1} proves that either the word $b^2a^2$ or $b^2ab^2$ $3$-compresses $\A$.
      \begin{figure}[ht]
        \centering
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$1$};
            \node[state] (q_2) [right of= q_1] {$1,x$};
            \node[state] (q_3) [right of= q_2] {$3,xa$};
            \node[state] (q) [right of= q_3,draw=none] {};
            \node[state,accepting] (q_4) [right of= q] {};
            \node[state] (q_5) [right of= q_4] {$1,2b$};

            \path[->] (q_0) edge node {$b$} (q_1)
                      (q_1) edge node {$b$} (q_2)
                      (q_2) edge node {$a$} (q_3)
                      (q_3) edge node {$a|xa\neq 2$} (q_4)
                      (q_3) edge [bend right=20] node [swap] {$b|xa=2,2b\neq 3$} (q_5)
                      (q_5) edge node [swap] {$b$} (q_4);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}\\
        \caption[]{P3MSA for the case $b={[x,3]}\backslash 1$ and $xa\neq 2$ or $2b\neq 3$.}
        \label{fig:prop:4-4:r:1}
      \end{figure}
  \item Let $b=[x,y]\backslash 2$, $3\not\in\{x,y\}$, $1\in\{x,y\}$ and $3b\in\{x,y\}$.
      There are two subcases.
      \begin{enumerate}
        \item Let $x=1$, then $b=[1,y]\backslash 2$, $y\neq 3$, $3b=y$ (as $2b=1$) and $2a\neq 1$ (as $3a=1$).
            So $\M(b^2a)=\{2a,3\}$ and if $2a\neq 2$, then $|\M(b^2a^2)|=3$, else if $2a= 2$, then $|\M(b^2ab)|=3$, so either the word $b^2a^2$ or $b^2ab$ $3$-compresses $\A$.
        \item Let $y=1$, then $b=[x,1]\backslash 2$, $x\neq 3$, $3b=1$ (as $2b=x$) and $2a\neq 1$ (as $3a=1$).
            If $2a=2$, then the P3MSA in Fig. \ref{fig:prop:4-4:r:4:1} proves that the word $a^2b^2$ $3$-compresses $\A$.
            If $2a\neq 2$, then the P3MSA in Fig. \ref{fig:prop:4-4:r:4:2} proves that the word $a^2ba^2$ $3$-compresses $\A$.
            \begin{figure}[ht]
                \centering
                \subfigure[][Case $2a=2$.]{
                \label{fig:prop:4-4:r:4:1}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=4.3em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$2$};
                    \node[state] (q_2) [right of= q_1] {$2,x$};
                    \node[state] (q_3) [right of= q_2] {$3,xa$};
                    \node[state,accepting] (q_4) [right of= q_3] {};

                    \path[->] (q_0) edge node {$b$} (q_1)
                              (q_1) edge node {$b$} (q_2)
                              (q_2) edge node {$a$} (q_3)
                              (q_3) edge node {$a$} (q_4)
                              (q_3) edge [bend left=10,draw=none] node {\phantom{$a|2a\neq 2$}} (q_4)
                              (q_3) edge [bend right=10,draw=none] node [swap] {\phantom{$b|2a= 2$}} (q_4);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}
                \hspace{15pt}
                \subfigure[][Case $2a\neq 2$.]{
                \label{fig:prop:4-4:r:4:2}
                {\footnotesize
                \begin{tikzpicture}[shorten >=1pt,node distance=4.3em,auto]

                    \node[state] (q_0) {};
                    \node[state] (q_1) [right of= q_0] {$1$};
                    \node[state] (q_2) [right of= q_1] {$1,3$};
                    \node[state] (q_3) [right of= q_2] {$1,2$};
                    \node[state] (q_4) [right of= q_3] {$3,2a$};
                    \node[state,accepting] (q_5) [right of= q_4] {};
                    \node[state] (q) [draw=none,right of= q_5] {};

                    \path[->] (q_0) edge node {$a$} (q_1)
                              (q_1) edge node {$a$} (q_2)
                              (q_2) edge node {$b$} (q_3)
                              (q_3) edge node {$a$} (q_4)
                              (q_4) edge node {$a$} (q_5);

                    \draw [->] (-.5,.5) -- (-.27,.27);

                \end{tikzpicture}}}\\
                \caption[]{P3MSA for the case $b={[x,1]}\backslash 2$, $x\neq 3$ and $3b\in\{x,1\}$.}
                \label{fig:prop:4-4:r:4}
            \end{figure}
      \end{enumerate}

  \item If $b=[x,3]\backslash 2$ and $xa\neq 2$ or $1b\neq 3$, then
      observe that $xa\neq 1$, as $3a=1$ and $x\neq 3$.
      If $xa\neq 2$, then $\M(b^2)=\{2,x\}$, $\M(b^2a)=\{3,xa\}$ and $|\M(b^2a^2)|=3$.
      If $xa=2$ and $1b\neq 3$, then $\M(a^2)=\{1,3\}$, $\M(a^2b)=\{1b,2\}$ and $|\M(a^2b^2)|=3$.
      Then either the word $b^2a^2$ or $a^2b^2$ $3$-compresses $\A$.
      If $b=[3,y]\backslash 2$ and $ya\neq 2$ or $1b\neq y$, then observe that $ya\neq 1$, as $3a=1$ and $y\neq 3$.
      The P3MSA in Fig. \ref{fig:prop:4-4:r:3} proves that either the word $a^2b^2$ or $a^2ba^2$ $3$-compresses $\A$.
      \begin{figure}[ht]
        \centering
        {\footnotesize
        \begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

            \node[state] (q_0) {};
            \node[state] (q_1) [right of= q_0] {$3$};
            \node[state] (q_2) [right of= q_1] {$1,3$};
            \node[state] (q) [right of= q_2,draw=none] {};
            \node[state] (q_3) [right of= q] {$2,1b$};
            \node[state,accepting] (q_4) [right of= q_3] {};
            \node[state] (q_6) [right of= q_4] {$3,ya$};
            \node[state] (q_5) [right of= q_6] {$2,y$};

            \path[->] (q_0) edge node {$a$} (q_1)
                      (q_1) edge node {$a$} (q_2)
                      (q_2) edge node {$b|1b\neq y$} (q_3)
                      (q_3) edge node {$b$} (q_4)
                      (q_2) edge [bend right=18] node [swap] {$b|1b=y,ya\neq 2$} (q_5)
                      (q_5) edge node [swap] {$a$} (q_6)
                      (q_6) edge node [swap] {$a$} (q_4);

            \draw [->] (-.5,.5) -- (-.27,.27);

        \end{tikzpicture}}\\
        \caption[]{P3MSA for the case $b={[3,y]}\backslash 2$ and $ya\neq 2$ or $1b\neq y$.}
        \label{fig:prop:4-4:r:3}
      \end{figure}
  \item Let $b=[x,3]\backslash z$, $z\not\in\{1,2\}$, $x\in\{1,2\}$ and $za\in\{1,2\}$.
      Observe that $z\neq 3$ and $3a=1$, so $za\neq 1$, and then it is always $za=2$.
      We have to consider two subcases.
      \begin{enumerate}
        \item Let $x=1$, then $b=[1,3]\backslash z$, $zb=1$, $3b\neq 1$ and $\M(a^2b)=\{z,3b\}$.
            If $3b\neq 2$, then $\M(a^2ba)=\{za,3ba,3\}$ and $a^2ba$ $3$-compresses $\A$.
            Else, if $3b=2$, then $\M(a^2b^2)=\{1,z,2b\}$ and $a^2b^2$ $3$-compresses $\A$.
        \item Let $x=2$, then $b=[2,3]\backslash z$, $3b\neq 2$ (as $zb=2$) and $\M(a^2b)=\{z,1b\}$.
            If $1b\neq 3$, then $\M(a^2b^2)=\{2,1b^2,z\}$ and $a^2b^2$ $3$-compresses $\A$.
            Else, if $1b=3$, then $\M(a^2ba)=\{za,1ba,3\}$ and $a^2ba$ $3$-compresses $\A$.\end{enumerate}\end{enumerate}\end{proof}

\FloatBarrier


TITLE: What's the normal cone to a union?
QUESTION [5 upvotes]: I have a reducible variety, $X = \bigcup_{i \in I} X_i \subset Y$, and I want to understand the normal cone $C_X Y$.
I write $X_J$ for $\cap_{j \in J} X_j$.

Can $C_X Y$ be expressed in terms of the $C_{X_J} X_K$?

(I take the convention $X_\emptyset = Y$ so that the $C_{X_i} Y$ are among the above.)
In fact in the example that has prompted this question, all the $X_J$ are smooth and connected, (though I do not know that they intersect transversely), and I am actually only interested in numerical information; i.e.,

Can the Segre class $S(X,Y)$ be expressed in terms of the Segre classes $S(X_J, X_K)$ for $J \subset K$ and perhaps also the intersection multiplicities of $X_M$ and $X_N$ along their intersection?

REPLY [2 votes]: No.  Take $X$ to be the union of two smooth, genus $0$ curves, say $X_1$ and $X_2$, that intersect in two nodes, say $p$ and $q$.  Then $\text{Pic}(X)$ is an extension of $\mathbb{Z}^2$ by $\mathbb{G}_m$.  So let $Y$ be a geometric $\mathbb{A}^1$-bundle over $X$ whose restriction to each of $X_1$ and $X_2$ is trivial, yet that is nontrivial on $X$.  Identify $X$ with the zero section of this $\mathbb{A}^1$-bundle.  The normal cone is a normal bundle, essentially just the data of $Y$ once again.  Yet you cannot recover $Y$ from its restriction to the two irreducible components.
Edit. Vivek clarified that he would also like to keep track of the restriction maps between the cones on different strata.  That would certainly make a difference in the example above.  However, if one allows non-transversal intersections, as Vivek explicitly allows, then there are still counterexamples.  For instance, consider a union of three concurrent lines in $\mathbb{P}^2$.  The irreducible components are each $\mathbb{P}^1$, and the intersections between components are all one (reduced) point.  Now there is simply no way to encode all invertible sheaves by the restriction on strata and restriction homomorphisms between them.  (Of course if one allows nilpotent thickenings of the strata, one could encode these invertible sheaves.)


TITLE: Help with summation stochastic
QUESTION [0 upvotes]: I don't understand how to get from the first line to the last. What happens to the summation? Please help! An important piece of information given in the question is that the transition probability from state 0 to state 1 is equal to 1. N.B. o(h) is just an error term that goes to 0 when divided  by h and a limit as h->0 is taken.
Thanks for the help!

REPLY [0 votes]: I think this is equal to $$(e^{\lambda h}-1)(1- \lambda h+o(h)) \ \ \ (1)$$
$$= e^{\lambda h}- \lambda h e^{\lambda h} + o(h) e^{\lambda h}-1+ \lambda h- o(h) \ \ \ (2)$$
$$ = e^{\lambda h}- \lambda h e^{\lambda h} + o(h) e^{\lambda h}-1+ \lambda h- o(h) \ \ \ (3)$$
Also we probably use the fact that the probabilities add up to $1$. And we know that $P(\xi_1 = 1| \xi_0 = 0) = 1$. This simplifies to $\lambda h+o(h)$ probably because we can combine terms to get one $o(h)$ term. Put $x = \lambda h$. So (3) is equal to:
$$ = \underbrace{e^{x}- xe^{x} -1}_{o(h) \ \text{term}}+ o(h) e^{x}+ \lambda h- o(h) \ \ \ (3)$$
$$ = \lambda h + o(h)$$


TITLE: Simplest way to calculate a determinant
QUESTION [1 upvotes]: The big $1$'s here just mean that the lower and upper triangular entries are all $1$'s. The trace entries are all zero. The matrix is for a general $n\times n$ matrix of this form. I'm trying to deduce a simpler relation.
$$\operatorname{det}~\begin{pmatrix} 0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 &\cdots & 1\\ 1 & 1 & 0 &\cdots & 1\\ \vdots & \vdots & \vdots & \ddots & 1\\ 1 & 1 & 1 & \cdots & 0\end{pmatrix}$$

REPLY [5 votes]: Here is a very bizarre solution. Let
$$A = \begin{pmatrix}1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{pmatrix} $$
be an $n \times n$ matrix whose entries are identically $1$. Then $A^{k} = n^{k-1} A$ and we have
$$ e^{t A} = I + \sum_{k=1}^{\infty} \frac{t^{k} n^{k-1}}{k!} A = I + \frac{e^{nt} - 1}{n} A. $$
But we know that
$$ \det e^{t A} = e^{\operatorname{tr}(t A)} = e^{nt}. $$
Thus if we put $ z = \frac{1}{n}(1 - e^{nt})$, then we have $z < \frac{1}{n}$ and
$$ \det ( I - z A ) = 1 - nz. $$
But both sides are polynomials in $z$, and thus it must coincide for all $z$. Therefore by plugging $z = 1$, we have
$$ \det (A - I) = (-1)^{n} \det ( I - A ) = (-1)^{n-1} (n - 1). $$

This argument can be used to prove that for any $\mathrm{u}, \mathrm{v} \in \Bbb{R}^n$, we have
$$ \det (I + \mathrm{u} \mathrm{v}^{t}) = 1 + \mathrm{u}^{t}\mathrm{v}, $$
a special case of the Sylvester's determinant theorem.