%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{31}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{paralist, xargs, hypcap, tikz, comment, hvfloat, cancel, mleftright}
\usetikzlibrary{trees, decorations, decorations.markings, shapes, arrows, matrix, calc, fit, intersections, patterns, angles, automata, positioning}
\usepackage[ruled,lined]{algorithm2e}
\usepackage{picins/picins}
\graphicspath{{figures/}}
\makeatletter\def\input@path{{figures/}}\makeatother
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Theorems, Proposition, etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{qu}[theorem]{Question}
\newtheorem{prob}[theorem]{Problem}
\newtheorem{definition}[theorem]{Definition}
%\theoremstyle{definition}
%\newtheorem{defn}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\Crefname{algocf}{Algorithm}{Algorithms}

% Symbols
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\fS}{\mathfrak{S}} % symmetric group

% Classical commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\left\langle \, #1 \; \middle| \; #2 \, \right\rangle} % dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\one}{\b{1}} % the all one vector
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % \eqdef
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:
\definecolor{darkblue}{rgb}{0.0,0.0,0.7}
\newcommand{\defn}[1]{\textsl{\color{darkblue} #1}} % emphasis of a definition
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\apriori}{\textit{a priori}} % a priori
\newcommand{\viceversa}{\textit{vice versa}} % vice versa
\newcommand{\versus}{\textit{vs.}~} % versus
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\perse}{\textit{per se}} % per se
\DeclareMathOperator{\inv}{inv} % inversions
\DeclareMathOperator{\ninv}{ninv} % number inversions
\DeclareMathOperator{\moveU}{moveU} % used in general pemutree sorting
\DeclareMathOperator{\moveD}{moveD}

% Special commands
\newcommand{\automatonA}{\mathbb{A}} % automaton A
\newcommand{\automatonP}{\mathbb{P}} % automaton P
\newcommand{\automatonU}{\mathbb{U}} % automaton U
\newcommand{\automatonD}{\mathbb{D}} % automaton D
\newcommand{\length}{\ell} % length
\newcommand{\generatingTree}{\mathcal{T}} % generating tree
\newcommand{\lexmin}{\mathcal{R}} % lexicographic minimal reduced words

% marginal comments
\usepackage{todonotes}
\newcommand{\vincent}[1]{\todo[color=blue!30]{\rm #1 \\ \hfill --- VPi.}}
\newcommand{\viviane}[1]{\todo[color=red!30]{\rm #1 \\ \hfill --- VPo.}}
\newcommand{\daniel}[1]{\todo[color=green!30]{\rm #1 \\ \hfill --- DTJ.}}

%% define your title in the usual way
\title{Permutree sorting}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp. by ANR CAPPS~17\,CE40\,0018 and CHARMS~19\,CE40\,0017.}\addressmark{1}, Viviane Pons\thanks{\href{mailto:viviane.pons@lri.fr}{viviane.pons@lri.fr}}\addressmark{2}, \and Daniel Tamayo Jim\'enez\thanks{\href{mailto:daniel.tamayo-jimenez@lri.fr}{daniel.tamayo-jimenez@lri.fr}}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, France \\
\addressmark{2}Universit\'e Paris-Saclay, CNRS, Laboratoire de recherche en informatique, Orsay, France
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Generalizing stack sorting and $c$-sorting for permutations, we define the permutree sorting algorithm.
Given two disjoint subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$, the $(U,D)$-permutree sorting tries to sort a permutation~$\pi \in \fS_n$ and fails if and only if there are~$1 \le i < j < k \le n$ such that~$\pi$ contains the subword~$jki$ with~$j \in U$ or~$kij$ with~$j \in D$.
This algorithm is seen as a way to explore an automaton which either rejects all reduced words of~$\pi$, or accepts those reduced words for~$\pi$ whose prefixes are all $(U,D)$-permutree sortable.
}

%% put your French abstract here, or comment this out if you don't have one
%\resumetitle{R\'esum\'e}
%\resume{
%G\'en\'eralisant les algorithmes du tri par pile et du $c$-tri, nous d\'efinissons l'algorithme du permutri.
%\'Etant donn\'es deux sous-ensembles disjoints~$U$ et~$D$ de $\{2, \dots, n-1\}$, l'algorithme de $(U,D)$-permutri tente de trier une permutation~${\pi \in \fS_n}$ et \'echoue si et seulement si il existe~$1 \le i < j < k \le n$ tels que~$\pi$ contienne un sous-mot~$jki$ avec~$j \in U$, ou~$kij$ avec~$j \in D$.
%Cet algorithme peut se voir comme l'exploration d'un automate qui rejette toutes les mots r\'eduits de~$\pi$, ou accepte pr\'ecis\'ement les mots r\'eduits de~$\pi$ dont tous les pr\'efixes sont~$(U,D)$-permutriables.
%}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{stack sorting, automata, permutrees, weak order}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{31Pilaud.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

The motivation of this paper is the classical family of \defn{stack-sortable} permutations introduced by D.~Knuth in his textbook~\cite[Sect.~2.2.1]{Knuth-TAOCP1} and characterized by the following equivalent conditions for a permutation~$\pi \in \fS_n$:
\begin{compactenum}[(i)]
\item \label{condition:stackSorting}
$\pi$ is sent to the identity by the stack sorting~$S$ defined by~$S(\tau n \rho) \eqdef S(\tau) S(\rho) n$.
%
\item \label{condition:patternStack}
$\pi$ avoids the pattern $231$ (\ie there is no~$p < q < r$ such that~$\pi_r < \pi_p < \pi_q$).
%
\item \label{condition:minimalLinearExtentionBinaryTree}
$\pi$ is minimal (minimal number of inversions) among all linear extensions of a binary tree on $n$ nodes (seen as a poset, labeled in inorder, oriented towards~its~root).
%$\pi$ is minimal (minimal number of inversions) among all linear extensions of a binary tree on $n$ nodes (seen as a poset, with the nodes labeled in inorder and the edges oriented towards the leaves).
%
\item \label{condition:alignedStack}
For $i < j < k$, the inversion set~$\inv(\pi) \eqdef \set{(\pi_p, \pi_q)}{p < q \text{ and } \pi_p > \pi_q}$ of~$\pi$ contains the inversion $(k,j)$ as soon as it contains the inversion~$(k,i)$.
%
\item \label{condition:sortableStack}
$\pi$ admits a reduced word of the form~$\pi = c_{I_1} \cdots c_{I_p}$ with nested~$I_1 \supseteq \dots \supseteq I_p$, where~$c_{\{i_1 < \dots < i_j\}} \eqdef s_{i_j} \cdots s_{i_1}$ is a product of the simple transpositions~$s_i \eqdef (i \;\; i+1)$.
\end{compactenum}

In his work on lattice congruences~\cite{Reading-CambrianLattices, Reading-CoxeterSortable, Reading-latticeCongruences}, N.~Reading defined  counterparts to conditions~\eqref{condition:minimalLinearExtentionBinaryTree}, \eqref{condition:alignedStack}, and~\eqref{condition:sortableStack} above, parametrized by the choice of a Coxeter element~$c$ in a finite Coxeter group~$W$: the minimality in $c$-Cambrian classes, the $c$-alignment, and the $c$-sortability.
%
In the situation of the symmetric group~$\fS_n$, we can think of a Coxeter element on~$\fS_n$ as an orientation of an $(n-1)$-path, or equivalently as a partition of~$\{2, \dots, n-1\}$ into two subsets~$U$ and~$D$.
The Cambrian analogues of the conditions~\eqref{condition:patternStack}, \eqref{condition:minimalLinearExtentionBinaryTree}, \eqref{condition:alignedStack} and~\eqref{condition:sortableStack} above are the following equivalent conditions for a permutation~$\pi \in \fS_n$:
\begin{compactenum}[(i')]
\addtocounter{enumi}{1}
%
\item \label{condition:patternCambrian}
For~$i < j < k$, the permutation~$\pi$ avoids the subword $jki$ if~$j \in U$ and~$kij$ if~$j \in D$.
%
\item \label{condition:minimalLinearExtentionCambrian}
$\pi$ is minimal among all linear extensions of a $c$-Cambrian tree on $n$ nodes~\cite{ChatelPilaud}.
%
\item \label{condition:alignedCambrian}
For~$i < j < k$, if~$\inv(\pi)$ contains~$(k,i)$, it contains $(k,j)$ if~$j \in U$ and $(j,i)$~if~$j \in D$.
%
\item \label{condition:sortableCambrian}
$\pi$ admits a reduced word of the form~$\pi = c_{I_1} \cdots c_{I_p}$ with nested~$I_1 \supseteq \ldots \supseteq I_p$, where~$c_I \eqdef c_{i_1} \cdots c_{i_{|I|}}$ is the subword of~$c \eqdef c_1 \cdots c_{n-1}$ indexed by~${I \eqdef \{i_1 \! < \! \dots \! < \! i_j\}}$.
\end{compactenum}

These Cambrian combinatorics motivated the introduction of permutree combinatorics~\cite{PilaudPons-permutrees}.
Permutrees generalize and interpolate between permutations, binary trees, and binary sequences, and explain the combinatorial, geometric, and algebraic similarities between them.
The data is now given by two subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$ that are not anymore required to form a partition of~$\{2, \dots, n-1\}$ (they may intersect and may not cover all the set).
It was proved in~\cite{PilaudPons-permutrees} that the conditions~(\ref{condition:patternCambrian}'), (\ref{condition:minimalLinearExtentionCambrian}'), and~(\ref{condition:alignedCambrian}') are still equivalent for a permutation~$\pi \in \fS_n$.
We call a permutation \defn{$(U,D)$-permutree minimal} when satisfying these conditions, \ie when it is minimal (minimal number of inversions) in its $(U,D)$-permutree class.
The objective of this paper is to discuss characterizations of the permutree minimal permutations in terms of their reduced words.
In other words, we aim at a condition playing the role of condition~(\ref{condition:sortableCambrian}') and equivalent to conditions~(\ref{condition:patternCambrian}'), (\ref{condition:minimalLinearExtentionCambrian}'), and~(\ref{condition:alignedCambrian}') for arbitrary subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$.

We first focus on the case where~$U = \varnothing$ and~$D = \{j\}$ for some~${j \in \{2, \dots, n-1\}}$, or the opposite.
To recognize the permutree minimal permutations in terms of their reduced words, we use two automata~$\automatonU(j)$ and $\automatonD(j)$ defined inductively in \cref{sec:proofPatternAvoidance} (we assume the reader familiar with basic automata theory, see \eg~\cite{HopcroftUllman}).
More precisely, a permutation contains no subword $jki$ (resp.~$kij$) with~$i < j < k$ if and only if it admits a reduced word accepted by the automaton~$\automatonU(j)$ (resp.~$\automatonD(j)$).
We moreover show in \cref{sec:algorithmicCombinatorialConsequences} that the sets of reduced words for a permutation~$\pi$ accepted by the automaton~$\automatonU(j)$ (resp.~$\automatonD(j)$) have a rich combinatorial structure.
This leads on the one hand to a simple algorithm to construct a reduced word for~$\pi$ accepted by~$\automatonU(j)$ (resp.~$\automatonD(j)$), and to a tree structure on the permutations containing no subword $jki$ (resp.~$kij$) with~$i < j < k$.

We then study the situation of arbitrary subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$.
In general, the reduced words accepted by the automata~$\automatonU(j)$ for each~$j \in U$ and by~$\automatonD(j)$ for each~$j \in D$ are distinct.
We prove however in \cref{sec:intersectionsAutomata} that there is a reduced word simultaneously accepted by all these automata when~$U$ and~$D$ are disjoint.
It implies that given any permutation~$\pi$ avoiding $jki$ if~$j \in U$ and~$kij$ if~$j \in D$, we can sort~$\pi$ while preserving these avoiding conditions.
We call \defn{$(U,D)$-permutree sorting} such a procedure, as they generalize the classical stack sorting.

When the subsets~$U$ and~$D$ partition~$\{2, \dots, n-1\}$, we actually show in \cref{sec:coxeterSortable} that the reduced word simultaneously accepted by the automata $\automatonU(j)$ for~${j \in U}$ and~$\automatonD(j)$ for~$j \in D$ is the $c$-sorting word of~$\pi$ as defined in~\cite{Reading-CoxeterSortable}.
This yields in particular an alternative proof that condition~(\ref{condition:sortableCambrian}') characterizes the Cambrian minimal permutations.

Finally, we discuss possible extensions to arbitrary finite Coxeter groups in \cref{sec:Coxeter}.

All proofs and details omitted here for space reasons can be found in~\cite{PilaudPonsTamayo}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Automata for reduced words}\label{sec:proofPatternAvoidance}

The \defn{symmetric group}~$\fS_n$ is generated by \defn{simple transpositions}~$s_i \eqdef (i \;\; i+1)$ for ${i \in [n-1]}$.
Each permutation~$\pi$ decomposes as products of transpositions of the form~$\pi = s_{i_1} \cdots s_{i_k}$. % with~$i_1, \dots, i_k \in [n-1]$.
The minimal number of transpositions in such a decomposition is the \defn{length}~$\ell(\pi)$ of~$\pi$ and the decompositions of length~$\ell(\pi)$ are the \defn{reduced words} for~$\pi$.

For a fixed~$j \in \{2, \dots, n-1\}$, we say that a permutation~$\pi$ \defn{avoids} $jki$ (resp.~$kij$) if for any~$i < j < k$, the word~$jki$ (resp.~$kij$) does not appear as a subword of the one-line notation of~$\pi$.
We insist on the fact that while the value~$j$ is fixed, $i$ and~$k$ take all possible values such that~$1 \le i < j < k \le n$.
This convenient notion here should not be mixed up with the notion of pattern avoidance where~$j$ is not fixed.
For instance, the permutation~$42135$ avoids~$2ki$, $3ki$, and~$4ki$ (and therefore the pattern~$231$), but contains~$ki3$ (and therefore the pattern~$312$) because its one-line notation contains~$423$. 

For~$j \in \{2, \dots, n-1\}$, we define inductively two \defn{automata}~$\automatonU(j)$ and $\automatonD(j)$ as shown in \cref{fig:automataRecursive}.
The induction stops at~$\automatonU(n)$ and~$\automatonD(1)$, which are defined by deleting the transitions~$s_n$ and~$s_0$ respectively in \cref{fig:automataRecursive}.
For instance, \cref{fig:automataComplete} shows the complete automata~$\automatonU(2)$ and $\automatonD(2)$ for~$n = 4$.
We call a state \defn{healthy}, \defn{ill}, or \defn{dead} depending on whether it belongs to the top, middle, or bottom row of the automata.
Each state has $n-1$ possible transitions, one for each $s_i$ for~$i \in [n-1]$, but we only explicitly indicate the ones between different states.
The automata $\automatonU(j)$ and $\automatonD(j)$ take as entry a reduced word~$s_{i_1} \cdots s_{i_\ell}$ for a permutation of~$\fS_n$ and read it from left to right.
We start at the initial state (marked with ``start''), and at step~$t$ we follow the transition marked by the letter~$s_{i_t}$ if any, or stay in the current state otherwise.
After~$\ell$ steps, the reduced word~$s_{i_1} \cdots s_{i_\ell}$ is accepted if the current state is accepting (doubly circled, healthy or ill states), and rejected otherwise (dead states).
The main tool of this paper is the following statement.

%\begin{figure}[b]
%	\centerline{
%		\scalebox{.85}{
%		\begin{tabular}{c@{\quad}c@{\quad}c@{\qquad}c}
%		$\automatonU(j)$ &
%		$\automatonD(j)$ &
%		$\automatonU(2)$ &
%		$\automatonD(2)$
%		\\[.1cm]
%		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=1cm, on grid, auto]
%			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
%			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.3cm of q_0] {}; 
%			\node[state,minimum size=0.5cm] (q_2) [below= 1.3cm of q_1] {}; 
%			\node (q_3) [right= 2cm of q_0] {$\automatonU(j+1)$};
%			\path[->] 
%				(q_0) edge node [swap] {$s_{j-1}$} (q_1)
%					  edge node {$s_j$} (q_3)
%				(q_1) edge node [swap] {$s_j$} (q_2);
%		\end{tikzpicture}
%		&
%		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto] 
%			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
%			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.3cm of q_0] {}; 
%			\node[state,minimum size=0.5cm] (q_2) [below= 1.3cm of q_1] {}; 
%			\node (q_3) [right= 2 cm of q_0] {$\automatonD(j-1)$};
%			\path[->] 
%				(q_0) edge node [swap] {$s_{j}$} (q_1)
%					  edge node {$s_{j-1}$} (q_3)
%				(q_1) edge node [swap] {$s_{j-1}$} (q_2);
%		\end{tikzpicture}
%		&
%		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto]
%			\node[state,initial,accepting,minimum size=0.5cm] (hj)   {}; 
%			\node[state,accepting,minimum size=0.5cm] (ij) [below= 1.3cm of hj] {}; 
%			\node[state,minimum size=0.5cm] (dj) [below= 1.3cm of ij] {}; 
%			%
%			\node[state,accepting,minimum size=0.5cm] (hj+1) [right= 1.3cm of hj] {};
%			\node[state,accepting,minimum size=0.5cm] (ij+1) [below= 1.3cm of hj+1] {}; 
%			\node[state,minimum size=0.5cm] (dj+1) [below= 1.3cm of ij+1] {}; 
%			%
%			\node[state,accepting,minimum size=0.5cm] (hj+2) [right= 1.3cm of hj+1] {};
%			\node[state,accepting,minimum size=0.5cm] (ij+2) [below= 1.3cm of hj+2] {}; 
%			\path[->] 
%				(hj) edge node [swap] {$s_1$} (ij)
%					   edge node {$s_2$} (hj+1)
%				(ij) edge node [swap] {$s_2$} (dj)
%				%
%				(hj+1) edge node [swap] {$s_2$} (ij+1)
%					 edge node {$s_3$} (hj+2)
%				(ij+1) edge node [swap] {$s_3$} (dj+1)
%				%
%				(hj+2) edge node [swap] {$s_3$} (ij+2);
%		\end{tikzpicture}
%		&
%		\begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto]
%			\node[state,initial,accepting,minimum size=0.5cm] (hj)   {}; 
%			\node[state,accepting,minimum size=0.5cm] (ij) [below= 1.3cm of hj] {}; 
%			\node[state,minimum size=0.5cm] (dj) [below= 1.3cm of ij] {}; 
%			%
%			\node[state,accepting,minimum size=0.5cm] (hj-1) [right= 1.3cm of hj] {};
%			\node[state,accepting,minimum size=0.5cm] (ij-1) [below= 1.3cm of hj-1] {}; 
%			\path[->] 
%				(hj) edge node [swap] {$s_2$} (ij)
%					   edge node {$s_1$} (hj-1)
%				(ij) edge node [swap] {$s_1$} (dj)
%				%
%				(hj-1) edge node [swap] {$s_1$} (ij-1);
%		\end{tikzpicture}
%		\end{tabular}
%		}
%	}
%	\caption{The automata $\automatonU(j)$ and $\automatonD(j)$ defined recursively (left), and the complete automata~$\automatonU(2)$ and $\automatonD(2)$ for $n=4$ (right).}
%	\label{fig:automataRecursive}
%\end{figure}

\begin{figure}[b]
	\centerline{
		$\automatonU(j) = $
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto, baseline=-1.7cm]
			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.6cm of q_0] {}; 
			\node[state,minimum size=0.5cm] (q_2) [below= 1.6cm of q_1] {}; 
			\node (q_3) [right= 2.3cm of q_0] {$\automatonU(j+1)$};
			\path[->] 
				(q_0) edge node [swap] {$s_{j-1}$} (q_1)
					  edge node {$s_j$} (q_3)
				(q_1) edge node [swap] {$s_j$} (q_2);
		\end{tikzpicture}
		\qquad\qquad
		$\automatonD(j) = $
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto, baseline=-1.7cm] 
			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.6cm of q_0] {}; 
			\node[state,minimum size=0.5cm] (q_2) [below= 1.6cm of q_1] {}; 
			\node (q_3) [right= 2.3cm of q_0] {$\automatonD(j-1)$};
			\path[->] 
				(q_0) edge node [swap] {$s_{j}$} (q_1)
					  edge node {$s_{j-1}$} (q_3)
				(q_1) edge node [swap] {$s_{j-1}$} (q_2);
		\end{tikzpicture}
	}
%	\caption{The automata $\automatonU(j)$ and $\automatonD(j)$ defined recursively (left), and the complete automata~$\automatonU(2)$ and $\automatonD(2)$ for $n=4$ (right).}
	\caption{Recursive definition of the automata $\automatonU(j)$ and $\automatonD(j)$.}
	\label{fig:automataRecursive}
\end{figure}

\begin{theorem}\label{thm:patternAvoidance}
Fix $j \in \{2, \dots, n-1\}$.
The following conditions are equivalent for~$\pi \in \fS_n$:
\begin{compactitem}
	\item $\pi$ admits a reduced word accepted by the automaton~$\automatonU(j)$ (resp.~$\automatonD(j)$),
	\item $\pi$ avoids $jki$ (resp.~$kij$).
\end{compactitem}
\end{theorem}

For example, the permutation $\pi = 3412$ avoids $2ki$ and $s_2 \cdot s_1 \cdot s_3 \cdot s_2$ is a reduced expression of $\pi$ accepted by~$\automatonU(2)$. On the other hand, $3241$ contains the subword $241$ and all its reduced expressions (such as $s_2 \cdot s_1 \cdot s_2 \cdot s_3$) are rejected by~$\automatonU(2)$.

\begin{figure}[t]
	\centerline{
		$\automatonU(2) =$
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto, baseline=-1.7cm]
			\node[state,initial,accepting,minimum size=0.5cm] (hj)   {}; 
			\node[state,accepting,minimum size=0.5cm] (ij) [below= 1.6cm of hj] {}; 
			\node[state,minimum size=0.5cm] (dj) [below= 1.3cm of ij] {}; 
			%
			\node[state,accepting,minimum size=0.5cm] (hj+1) [right= 1.6cm of hj] {};
			\node[state,accepting,minimum size=0.5cm] (ij+1) [below= 1.6cm of hj+1] {}; 
			\node[state,minimum size=0.5cm] (dj+1) [below= 1.3cm of ij+1] {}; 
			%
			\node[state,accepting,minimum size=0.5cm] (hj+2) [right= 1.6cm of hj+1] {};
			\node[state,accepting,minimum size=0.5cm] (ij+2) [below= 1.6cm of hj+2] {}; 
			\path[->] 
				(hj) edge node [swap] {$s_1$} (ij)
					   edge node {$s_2$} (hj+1)
				(ij) edge node [swap] {$s_2$} (dj)
				%
				(hj+1) edge node [swap] {$s_2$} (ij+1)
					 edge node {$s_3$} (hj+2)
				(ij+1) edge node [swap] {$s_3$} (dj+1)
				%
				(hj+2) edge node [swap] {$s_3$} (ij+2);
		\end{tikzpicture}
		\qquad\qquad
		$\automatonD(2) = $		
		\begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto, baseline=-1.7cm]
			\node[state,initial,accepting,minimum size=0.5cm] (hj)   {}; 
			\node[state,accepting,minimum size=0.5cm] (ij) [below= 1.6cm of hj] {}; 
			\node[state,minimum size=0.5cm] (dj) [below= 1.3cm of ij] {}; 
			%
			\node[state,accepting,minimum size=0.5cm] (hj-1) [right= 1.6cm of hj] {};
			\node[state,accepting,minimum size=0.5cm] (ij-1) [below= 1.6cm of hj-1] {}; 
			\path[->] 
				(hj) edge node [swap] {$s_2$} (ij)
					   edge node {$s_1$} (hj-1)
				(ij) edge node [swap] {$s_1$} (dj)
				%
				(hj-1) edge node [swap] {$s_1$} (ij-1);
		\end{tikzpicture}
	}
	\caption{The complete automata~$\automatonU(2)$ and $\automatonD(2)$ for $n=4$.}
	\label{fig:automataComplete}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Structure of accepted reduced words}\label{sec:algorithmicCombinatorialConsequences}

\subsection{The set of accepted reduced words}\label{subsec:principles}

Observe that a given permutation~$\pi$ may admit both accepted and rejected reduced words.
For instance, the transposition~${(j-1 \;\; j+1)}$ has reduced words~$s_j \cdot s_{j-1} \cdot s_j$ accepted by~$\automatonU(j)$ and~$s_{j-1} \cdot s_j \cdot s_{j-1}$ rejected by~$\automatonU(j)$.
However, the set of accepted reduced words satisfies the following properties.

\begin{proposition}[Who can do more can do less!]\label{prop:prefixesReducedExpressions}
The set of reduced words accepted by~$\automatonU(j)$ (resp.~$\automatonD(j)$) is closed by taking prefix.
\end{proposition}

\begin{comment}
\begin{proof}
This immediately follows from the fact that the set of reduced words is closed by prefix, and that the set of accepting states of~$\automatonU(j)$ is connected and contains the initial state.
\end{proof}
\end{comment}

\begin{proposition}[When health goes, everything goes!]\label{prop:algorithm}
If $\pi$ admits an accepted reduced expression, then $\pi$ admits an accepted reduced expression starting with any descent that remains in the healthy states. In other words, let $\ell \in [n-1]$ distinct from $j-1$ (resp.~$j$).
If~$\pi \in \fS_n$ avoids $jki$ (resp.~$kij$) and reverses $\ell$ and $\ell+1$, it admits a reduced word starting with $s_\ell$ and accepted by~$\automatonU(j)$ (resp.~$\automatonD(j)$).
\end{proposition}

\begin{comment}
\begin{proof}
Since $\pi$ reverses $\ell$ and $\ell+1$, it admits a reduced word of the form~$\pi = s_\ell \cdot \tau$. Now consider two cases depending on the value of $\ell$:
\begin{compactitem}
	\item If $\ell = j$, then $\tau$ avoids $(j+1)ki$ by \cref{lem:vincent4}\,(2), thus $\tau$ has a reduced word accepted by $\automatonU(j+1)$ by \cref{thm:patternAvoidance}, and we conclude by \cref{lem:vincent4}\,(1).
	\item Otherwise, $\ell$ is neither $j-1$ nor $j$, so that $\tau$ avoids $jki$ by \cref{lem:vincent2}\,(2), thus $\tau$ has a reduced word accepted by $\automatonU(j)$ by \cref{thm:patternAvoidance}, and we conclude by \cref{lem:vincent2}\,(1).
	\qedhere
\end{compactitem}
\end{proof}
\end{comment}

\begin{proposition}[All roads lead to Rome!]\label{prop:sameStateAcceptedReducedExpressions}
Given a permutation $\pi \in \fS_n$, all the reduced words for~$\pi$ accepted by $\automatonU(j)$ (resp.~$\automatonD(j)$) end at the same state.
\end{proposition}

\subsection{Finding accepted reduced words}

\cref{prop:algorithm} has a strong algorithmic consequence.
Imagine we want to test whether a permutation~$\pi \in \fS_n$ is minimal in its permutree class for~$U = \{j\}$ and~$D = \varnothing$.
Of course, the quickest way is to check for all~$i < j < k$ whether~$\pi$ contains the subword~$jki$.
But since this interpretation will be lost beyond type~$A$, let us impose the use of reduced words for~$\pi$ to make this test.
While it would be \apriori{} necessary to check all reduced words on the automaton~$\automatonU(j)$, \cref{prop:algorithm} enables us to construct without loss of generality a reduced word for~$\pi$ and we will just need to check if this one is accepted by~$\automatonU(j)$.
Somewhat dually, one can also construct a reduced word accepted by~$\automatonU(j)$ that is a reduced word for~$\pi$ if and only if~$\pi$ avoids~$jki$.
This is done in the following algorithm, that we call \defn{$(\{j\}, \varnothing)$-permutree sorting}.

\bigskip
\IncMargin{1em}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\SetKwFor{Repeat}{repeat}{}{}
\SetKwIF{If}{ElseIf}{Else}{if}{then}{else if}{else}{}
\DontPrintSemicolon
\DecMargin{.7cm}
\begin{algorithm}[H]
	\Input{a permutation $\pi \in \fS_n$ and an integer~$j \in [n]$}
	\Output{a reduced word accepted by~$\automatonU(j)$, candidate reduced word for~$\pi$}
	
	$w \eqdef \varepsilon$ \;
	\Repeat{}{
		\If{$\exists \; \ell \ne j-1$ such that $\ell$ and $\ell+1$ are reversed in~$\pi$}{
			$\pi \eqdef s_\ell \cdot \pi$, \quad $w \eqdef w \cdot s_\ell$ \;
			\lIf{$\ell = j$}{
				$j \eqdef j+1$
			}
		}
	}
	\If{$j-1$ and $j$ are reversed in~$\pi$}{
		$\pi \eqdef s_{j-1} \cdot \pi$, \quad $w \eqdef w \cdot s_{j-1}$ \;
		$w \eqdef w \cdot w' \cdot w''$ where~$w'$ sorts~$\pi_{[j]}$ and $w''$ sorts $\pi_{[n] \ssm [j]}$ \;
	}
	\Return $w$ \;
	\caption{$(\{j\}, \varnothing)$-permutree sorting}
	\label{algo:shortcutsUj}
\end{algorithm}

\medskip
\begin{corollary}\label{coro:algorithm}
For any permutation~$\pi$ and~$j \in \{2, \dots, n-1\}$, \cref{algo:shortcutsUj} returns a reduced~word~$w$ accepted by $\automatonU(j)$ such that~$w$ is a reduced word for~$\pi$ if and only if~$\pi$ avoids~$jki$.
\end{corollary}

\begin{example}\label{exm:algo1}
	Let us present the $(\{2\},\varnothing)$-permutree sorting algorithm in action for the permutations~$\pi_1 \eqdef 3421$ and~$\pi_2 \eqdef 4231$. The steps of the algorithm are presented in the table below. Each row contains the states of the permutation~$\pi$ and of the word~$w$ and the current values of~$j$ and~$\ell$ in use at each step. Notice that for~$\pi_1 \eqdef 3421$ the algorithm ends with the identity, which coincides with the fact that~$\pi_1 \eqdef 3421$ avoids~$2ki$. In contrast, for~$\pi_2 \eqdef 4231$ the algorithm ends with the permutation~$1243$, which coincides with the fact that~$\pi_2 \eqdef 4231$ contains~$2ki$. 
	
	\medskip
	\centerline{
		\begin{tabular}[t]{l|l|c|c}
			$\pi_1$ & $w_1$ & $j_1$ & $\ell_1$ \\
			\hline
			$3421$ & $\varepsilon$ & $2$ & $2$ \\
			$2431$ & $s_2$ & $3$ & $1$ \\
			$1432$ & $s_2 \cdot s_1$ & $3$ & $3$ \\
			$1342$ & $s_2 \cdot s_1 \cdot s_3$ & $4$ & $2$ \\
			$1243$ & $s_2 \cdot s_1 \cdot s_3 \cdot s_2$ & $4$ & $3$ \\
			$1234$ & $s_2 \cdot s_1 \cdot s_3 \cdot s_2 \cdot s_3$ & $4$ &
		\end{tabular}
		\qquad\qquad
		\begin{tabular}[t]{l|l|c|c}
			$\pi_2$ & $w_2$ & $j_2$ & $\ell_2$ \\
			\hline
			$4231$ & $\varepsilon$ & $2$ & $3$ \\
			$3241$ & $s_3$ & $2$ & $2$ \\
			$2341$ & $s_3 \cdot s_2$ & $3$ & $1$ \\
			$1342$ & $s_3 \cdot s_2 \cdot s_1$ & $3$ & $2$ \\
			$1243$ & $s_3 \cdot s_2 \cdot s_1 \cdot s_2$ & $3$ &
		\end{tabular}
		}
	
	\medskip
	\noindent
\end{example}               

\subsection{Generating trees on accepted reduced words}\label{subsec:trees}

\cref{prop:prefixesReducedExpressions,prop:sameStateAcceptedReducedExpressions} also have a relevant consequence, which is more combinatorial this time.
Namely, they naturally define generating trees for the $(\{j\}, \varnothing)$-permutree minimal permutations, following certain special reduced words for them.
To construct these trees, pick an arbitrary priority order~$\prec$ on~$\{s_1, \dots, s_{n-1}\}$.
For a $(\{j\}, \varnothing)$-permutree minimal permutation~$\pi \in \fS_n$, denote by~$\pi(\{j\}, \varnothing, \prec)$ the $\prec$-lexicographic minimal reduced word for~$\pi$ that is accepted by~$\automatonU(j)$.
Denote by~$\lexmin(n, \{j\}, \varnothing, \prec)$ the set of reduced words of the form~$\pi(\{j\}, \varnothing, \prec)$ for all $(\{j\}, \varnothing)$-permutree minimal permutations~$\pi \in \fS_n$.
The following statement is an analogue of \cref{prop:prefixesReducedExpressions}.

\begin{proposition}\label{prop:generatingTrees}
The set $\lexmin(n, \{j\}, \varnothing, \prec)$ is closed by prefix.
\end{proposition}

\begin{comment}
\begin{proof}
Consider a reduced word~$w = u \cdot v$ where~$u$ is not in~$\lexmin(n, \{j\}, \varnothing, \prec)$.
If~$u$ is not accepted by~$\automatonU(j)$, neither is~$w$ by \cref{prop:prefixesReducedExpressions}.
Otherwise, there exists a reduced word~$u'$ representing the same permutation as~$u$, accepted by~$\automatonU(j)$ and $\prec$-lexicographic smaller than~$u$.
By \cref{prop:sameStateAcceptedReducedExpressions}, the reduced words~$u$ and~$u'$ end at the same state of~$\automatonU(j)$.
Therefore, if~$w = u \cdot v$ is accepted by~$\automatonU(j)$, so is~$u' \cdot v$.
Since~$u' \cdot v$ is $\prec$-lexicographically smaller than~$u \cdot v$ and represents the same permutation, this ensures that~$w$ is not in~$\lexmin(n, \{j\}, \varnothing, \prec)$.
\end{proof}
\end{comment}

\parpic(5.5cm,5.5cm)(-10pt, 170pt)[r][b]{
    	\begin{tikzpicture}[xscale=1, yscale=0.65, color=lightgray]
    		\node[blue](P1234) at (0,0){1234};
    		%
    		\node[blue](P2134) at (-1,1.5){2134};
    		\node[blue](P1324) at ( 0,1.5){1324};
    		\node[blue](P1243) at ( 1,1.5){1243};
    		%
    		\node(P2314) at (-2,3){2314};
    		\node[blue](P3124) at (-1,3){3124};
    		\node[blue](P2143) at ( 0,3){2143};
    		\node[blue](P1342) at ( 1,3){1342};
    		\node[blue](P1423) at ( 2,3){1423};
    		%
    		\node[blue](P3214) at (-2.5,4.5){3214};
    		\node(P2341) at (-1.5,4.5){2341};
    		\node[blue](P3142) at (-0.5,4.5){3142};
    		\node(P2413) at ( 0.5,4.5){2413};
    		\node[blue](P4123) at ( 1.5,4.5){4123};
    		\node[blue](P1432) at ( 2.5,4.5){1432};
    		%
    		\node(P3241) at (-2,6){3241};
    		\node(P2431) at (-1,6){2431};
    		\node[blue](P3412) at ( 0,6){3412};
    		\node[blue](P4213) at ( 1,6){4213};
    		\node[blue](P4132) at ( 2,6){4132};
    		%
    		\node[blue](P3421) at (-1,7.5){3421};
    		\node(P4231) at ( 0,7.5){4231};
    		\node[blue](P4312) at ( 1,7.5){4312};
    		%
    		\node[blue](P4321) at (0,9){4321};
    		%
    		%
    		\draw[line width=0.5mm,blue](P1234) -- (P2134);
    		\draw[line width=0.5mm,red](P1234) -- (P1324);
    		\draw[line width=0.5mm,green](P1234) -- (P1243);
    		%
    		\draw(P2134) -- (P2314);
    		\draw[line width=0.5mm,green](P2134) -- (P2143);
    		\draw[line width=0.5mm,blue](P1324) -- (P3124);
    		\draw[line width=0.5mm,green](P1324) -- (P1342);
    		\draw(P1243) -- (P2143);
    		\draw[line width=0.5mm,red](P1243) -- (P1423);
    		%
    		\draw(P2314) -- (P3214);
    		\draw(P2314) -- (P2341);
    		\draw[line width=0.5mm,red](P3124) -- (P3214);
    		\draw[line width=0.5mm,green](P3124) -- (P3142);
    		\draw(P2143) -- (P2413);
    		\draw(P1342) -- (P3142);
    		\draw[line width=0.5mm,red](P1342) -- (P1432);
    		\draw[line width=0.5mm,blue](P1423) -- (P4123);
    		\draw(P1423) -- (P1432);
    		%
    		\draw(P3214) -- (P3241);
    		\draw(P2341) -- (P3241);
    		\draw(P2341) -- (P2431);
    		\draw[line width=0.5mm,red](P3142) -- (P3412);
    		\draw(P2413) -- (P4213);
    		\draw(P2413) -- (P2431);
    		\draw[line width=0.5mm,red](P4123) -- (P4213);
    		\draw(P4123) -- (P4132);
    		\draw[line width=0.5mm,blue](P1432) -- (P4132);
    		%
    		\draw(P3241) -- (P3421);
    		\draw(P2431) -- (P4231);
    		\draw[line width=0.5mm,blue](P3412) -- (P4312);
    		\draw[line width=0.5mm,green](P3412) -- (P3421);
    		\draw(P4213) -- (P4231);
    		\draw(P4132) -- (P4312);
    		%
    		\draw(P3421) -- (P4321);
    		\draw(P4231) -- (P4321);
    		\draw[line width=0.5mm,green](P4312) -- (P4321);	
    	\end{tikzpicture}
}
{
This yields a natural generating tree for ${\lexmin(n, \{j\}, \varnothing, \prec)}$ where the parent of a reduced word~$w$ is obtained by deleting its last letter.
Replacing each reduced word by the corresponding permutation, this provides a generating tree for the $(\{j\}, \varnothing)$-permutree minimal permutations of~$\fS_n$.
We have represented this tree on the right for~$j = 2$ with the priority order~$s_1 \prec s_2 \prec s_3$.
It is natural to draw these trees on top of the Hasse diagram of the right weak order on permutations.
The edges of the trees corresponding to the right multiplications by $s_1$, $s_2$ and $s_3$ are colored by blue, red, and green respectively.
%Generating trees are useful for efficient exhaustive and random generation.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Intersection of automata}\label{sec:intersectionsAutomata}

\subsection{A common reduced word}

We now consider arbitrary subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$.
We already know from~\cite{PilaudPons-permutrees} and \cref{thm:patternAvoidance} that the following conditions are equivalent for~$\pi \in \fS_n$:
\begin{compactenum}[(i)]
	\item the permutation $\pi$ is minimal in its~$(U,D)$-permutree class, 
	\item for~$i < j < k$, the permutation $\pi$ avoids the subword~$jki$ if~$j \in U$ and~$kij$ if~$j \in D$,
	\item for each~$j \in U$ (each~$j \in D$), there is a reduced word for~$\pi$ accepted by~$\automatonU(j)$ (resp.~by~$\automatonD(j)$).
\end{compactenum}
A natural question is whether there is a reduced word simultaneously accepted by all these automata.
We start with an example showing that this is not always the case.

\begin{example}\label{exm:problemUDintersect}
For~$j \in \{2, \dots, n-1\}$, let $U = \{j\} = D$ and~${\pi = s_{j-1} \cdot s_j \cdot s_{j-1} = s_j \cdot s_{j-1} \cdot s_j}$.
Then, the word~$s_{j-1} \cdot s_j \cdot s_{j-1}$ is accepted by $\automatonD(j)$ but not by~$\automatonU(j)$, while the word $s_j \cdot s_{j-1} \cdot s_j$ is accepted by $\automatonU(j)$ but not by~$\automatonD(j)$.
\end{example}

This example clearly extends to all subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$ with a non-empty intersection.
In contrast, this situation cannot occur when~$U$ and~$D$ are disjoint.

\begin{theorem}\label{thm:permutreeMinimal}
Consider two disjoint subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$.
The following conditions are equivalent for~$\pi \in \fS_n$:
\begin{compactitem}
	\item $\pi$ admits a reduced word accepted by all automata~$\automatonU(j)$ for~$j \in U$ and~$\automatonD(j)$ for~${j \in D}$,
	\item $\pi$ avoids $jki$ for all~$j \in U$ and~$kij$ for all~$j \in D$.
\end{compactitem}
\end{theorem}

\subsection{Intersection of automata}

\cref{thm:permutreeMinimal} can be rephrased in terms of intersection of automata.
Recall that the intersection of some automata~$\automatonA_1, \dots, \automatonA_p$ is the automaton~$\automatonA = \bigcap_{i \in [p]} \automatonA_i$ such that a word is accepted by~$\automatonA$ if and only if it is accepted by all~$\automatonA_1, \dots, \automatonA_p$.
A state of the automaton~$\automatonA$ is $p$-tuple formed by states of the automata~$\automatonA_1, \dots, \automatonA_p$, and a transition~$t$ simultaneously changes all entries of the $p$-tuple corresponding to states modified by~$t$.
See~\cite[p.\,59--60]{HopcroftUllman} for details.
We denote by~$\automatonP(U,D)$ the intersection of the automata~$\automatonU(j)$ for~$j \in U$ and~$\automatonD(j)$ for~$j \in D$.
We thus obtain the following statement.

\begin{corollary}
\label{coro:permutreeMinimal}
When~$U$ and~$D$ are disjoint, the following conditions are equivalent for~$\pi \in \fS_n$:
\begin{compactitem}
	\item $\pi$ admits a reduced word accepted by the automaton~$\automatonP(U,D)$,
	\item $\pi$ contains no subword~$jki$ if~$j \in U$ and~$kij$ if~$j \in D$ with~$i < j < k$.
\end{compactitem}
\end{corollary}

We say that a state of~$\automatonP(U,D)$ is \defn{healthy} (resp.~\defn{ill}, resp.~\defn{dead}) when the corresponding states in~$\automatonU(j)$ for~$j \in U$ and~$\automatonD(j)$ for~$j \in D$ are all healthy (resp.~contain at least one ill state, but no dead one, resp.~contains at least one dead state).

\subsection{The set of accepted reduced words of~$\automatonP(U,D)$}

Applying the principles of \cref{subsec:principles} to each automaton~$\automatonU(j)$ for~$j \in U$ and~$\automatonD(j)$ for~${j \in D}$, we derive similar principles for the automaton~$\automatonP(U,D)$.

\begin{proposition}\label{prop:prefixesReducedExpressionsIntersection}
The set of reduced words accepted by~$\automatonP(U,D)$ is closed by prefix.
\end{proposition}

\begin{proposition}\label{prop:algorithmIntersection}
If a permutation~$\pi$ avoids~$jki$ for~$j \in U$ and~$kij$ for~$j \in D$, and admits a reduced word starting with~$s_\ell$ such that the transition~$s_\ell$ leads to an healthy state of~$\automatonP(U,D)$, then it admits a reduced word starting with~$s_\ell$ and accepted by~$\automatonP(U,D)$.
\end{proposition}

\begin{proposition}\label{prop:sameStateAcceptedReducedExpressionsIntersection}
Given a permutation $\pi \in \fS_n$, all the reduced words for~$\pi$ accepted by $\automatonP(U,D)$ end at the same state.
\end{proposition}

\subsection{Permutree sorting}\label{subsec:permutreeSorting}

We now generalize \cref{algo:shortcutsUj} to the following \defn{$(U,D)$-permutree sorting algorithm}.
As in \cref{algo:shortcutsUj}, the algorithm will read the automaton~$\automatonP(U,D)$ without actually constructing it.
To virtually follow the edges of the automaton~$\automatonP(U,D)$, we use the following two operations on our sets~$U$ and~$D$:
\begin{compactitem}
\item $\moveU(U,\ell)$ is~$U$ if~$\ell \notin U$ and $(U \ssm \{ \ell \}) \cup \{ \ell + 1 \}$ if~$\ell \in U$, 
\item $\moveD(D,\ell)$ is~$D$ if~$\ell + 1 \notin D$ and $(D \ssm \{ \ell + 1 \}) \cup \{ \ell \}$ if~$\ell + 1 \in D$.
\end{compactitem}
In contrast to \cref{algo:shortcutsUj}, we have opted here for a recursive style.

\bigskip
\IncMargin{1em}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\SetKwFor{Repeat}{repeat}{}{}
\SetKwIF{If}{ElseIf}{Else}{if}{then}{else if}{else}{}
\SetKwProg{Fn}{Function}{}{}
\DontPrintSemicolon
\DecMargin{.7cm}
\begin{algorithm}[H]
	\Fn{{\rm permutreeSort$(\pi, U, D)$}}{
	\Input{a permutation $\pi \in \fS_n$ and two disjoint subsets~$U$ and~$D$ of~$[n]$}
	\Output{a reduced word accepted by~$\automatonP(U,D)$, candidate reduced word for~$\pi$}
	\If{$\exists \; \ell \in [n-1]$ such that $\ell$ and $\ell+1$ are reversed in~$\pi$, and $\ell+1 \notin U$ and~$\ell \notin D$}{
		\Return $s_\ell \cdot \text{permutreeSort}(s_\ell \cdot \pi, \; \moveU(U, \ell), \; \moveD(D,\ell))$ \;
	}
	\If{$\exists \; \ell \in [n-1]$ such that $\ell$ and $\ell+1$ are reversed in~$\pi$,
	\\ and ($\ell + 1 \notin U$ or $\pi([\ell+1]) = [\ell +1]$) and ($\ell \notin D$ or $\pi([\ell -1]) = [\ell - 1]$)
	}{
		\Return $s_\ell \cdot \text{permutreeSort}(s_\ell \cdot \pi, \; \moveU(U \ssm \{ \ell + 1 \}, \ell), \; \moveD(D \ssm \{ \ell \},\ell))$ \;
	}
	\Return $\varepsilon$ \;
	}
	\caption{$(U,D)$-permutree sorting}
	\label{algo:permutreeSorting}
\end{algorithm}
\bigskip

Note that in \cref{algo:permutreeSorting}, we could ignore~$n$ in the list~$U$ (resp.~$1$ in the list~$D$) since~$\automatonU(n)$ (resp.~$\automatonD(1)$) accepts all reduced words.
We have decided not to do it to be coherent with our recursive definition of~$\automatonU(j)$ and~$\automatonD(j)$.

\begin{corollary}\label{coro:algorithmIntersection}
For any permutation~$\pi$ and any disjoint subsets~$U$ and~$D$ of~$\{2, \dots, n-1\}$, \cref{algo:permutreeSorting} returns a reduced word~$w$ accepted by $\automatonP(U,D)$ such that~$w$ is a reduced word for~$\pi$ if and only if~$\pi$ avoids~$jki$ for~$j \in U$ and~$kij$ for~$j \in D$.
\end{corollary}

\parpic(7.8cm,5cm)(0pt, 15pt)[r][b]{
	\begin{tabular}[t]{l|l|c|c|c|c}
		$\pi_1$ & $w_1$ & $U_1$ & $D_1$ & $\ell_1$ & $k_1$ \\
		\hline
		$3214$ & $\varepsilon$ & $\{3\}$ & $\{2\}$ & $1$ & . \\
		$3124$ & $s_1$ & $\{3\}$ & $\{1\}$ & $2$ & $3$ \\
		$2134$ & $s_1 \cdot s_2$ & $\varnothing$ & $\{1\}$ & $1$ & $0$ \\
		$1234$ & $s_1 \cdot s_2 \cdot s_1$ & & &
		\\
		\multicolumn{5}{c}{}
		\\[-.4cm]
		$\pi_2$ & $w_2$ & $U_2$ & $D_2$ & $\ell_2$ & $k_2$ \\
		\hline
		$1324$ & $\varepsilon$ & $\{3\}$ & $\{2\}$ & $2$ & $1$, $3$ \\
		$1234$ & $s_2$ & & &
		\\
		\multicolumn{5}{c}{}
		\\[-.4cm]
		$\pi_3$ & $w_3$ & $U_3$ & $D_3$ & $\ell_3$ & $k_3$ \\
		\hline
		$1342$ & $\varepsilon$ & $\{3\}$ & $\{2\}$ & $2$ & $1$, \textcolor{red}{$\xcancel{\textcolor{black}{3}}$}
	\end{tabular}
}
{\begin{example}\label{exm:algo2}
	The tables on the right present the $(\{3\},\{2\})$-permutree sorting algorithm in action for the permutations~$\pi_1 \eqdef 3214$, $\pi_2 \eqdef 1324$ and~$\pi_3 \eqdef 1342$. 
	Each row in these tables contains the states of the permutation~$\pi$ and of the word~$w$, the current values of~$j$ and~$\ell$ in use at each step, and the values of~$k$ for which we have to check that~$\pi([k]) = [k]$, crossed in red when it fails. These tables show that~$\pi_1$ and~$\pi_2$ are $(\{3\},\{2\})$-permutree sortable while $\pi_3$ is not (as it contains~$3ki$).
\end{example}}

%\begin{remark}
%The $(U,D)$-permutree sorting algorithm is a sorting procedure such that
%\begin{compactitem}
%\item applied to an $(U,D)$-permutree minimal permutation~$\pi$, it only passes through $(U,D)$-permutree minimal permutations and arrives to the identity permutation, 
%\item it fails to sort a non $(U,D)$-permutree minimal permutation~$\pi$.
%\end{compactitem}
%In this sense, it is a direct generalization of the stack sorting algorithm.
%\end{remark}

\subsection{Generating trees}

\parpic(5.5cm,10cm)(-10pt, 140pt)[r][b]{
	\begin{minipage}{5cm}
		\begin{tikzpicture}[xscale=1, yscale=0.65, color=lightgray]
			\node[blue](P1234) at (0,0){1234};
			%
			\node[blue](P2134) at (-1,1.5){2134};
			\node[blue](P1324) at ( 0,1.5){1324};
			\node[blue](P1243) at ( 1,1.5){1243};
			%
			\node(P2314) at (-2,3){2314};
			\node[blue](P3124) at (-1,3){3124};
			\node[blue](P2143) at ( 0,3){2143};
			\node(P1342) at ( 1,3){1342};
			\node[blue](P1423) at ( 2,3){1423};
			%
			\node[blue](P3214) at (-2.5,4.5){3214};
			\node(P2341) at (-1.5,4.5){2341};
			\node(P3142) at (-0.5,4.5){3142};
			\node(P2413) at ( 0.5,4.5){2413};
			\node[blue](P4123) at ( 1.5,4.5){4123};
			\node[blue](P1432) at ( 2.5,4.5){1432};
			%
			\node(P3241) at (-2,6){3241};
			\node(P2431) at (-1,6){2431};
			\node(P3412) at ( 0,6){3412};
			\node[blue](P4213) at ( 1,6){4213};
			\node[blue](P4132) at ( 2,6){4132};
			%
			\node(P3421) at (-1,7.5){3421};
			\node(P4231) at ( 0,7.5){4231};
			\node[blue](P4312) at ( 1,7.5){4312};
			%
			\node[blue](P4321) at (0,9){4321};
			%
			%
			\draw[line width=0.5mm,blue](P1234) -- (P2134);
			\draw[line width=0.5mm,red](P1234) -- (P1324);
			\draw[line width=0.5mm,green](P1234) -- (P1243);
			%
			\draw(P2134) -- (P2314);
			\draw[line width=0.5mm,green](P2134) -- (P2143);
			\draw[line width=0.5mm,blue](P1324) -- (P3124);
			\draw(P1324) -- (P1342);
			\draw(P1243) -- (P2143);
			\draw[line width=0.5mm,red](P1243) -- (P1423);
			%
			\draw(P2314) -- (P3214);
			\draw(P2314) -- (P2341);
			\draw[line width=0.5mm,red](P3124) -- (P3214);
			\draw(P3124) -- (P3142);
			\draw(P2143) -- (P2413);
			\draw(P1342) -- (P3142);
			\draw(P1342) -- (P1432);
			\draw[line width=0.5mm,blue](P1423) -- (P4123);
			\draw[line width=0.5mm,green](P1423) -- (P1432);
			%
			\draw(P3214) -- (P3241);
			\draw(P2341) -- (P3241);
			\draw(P2341) -- (P2431);
			\draw(P3142) -- (P3412);
			\draw(P2413) -- (P4213);
			\draw(P2413) -- (P2431);
			\draw[line width=0.5mm,red](P4123) -- (P4213);
			\draw[line width=0.5mm,green](P4123) -- (P4132);
			\draw(P1432) -- (P4132);
			%
			\draw(P3241) -- (P3421);
			\draw(P2431) -- (P4231);
			\draw(P3412) -- (P4312);
			\draw(P3412) -- (P3421);
			\draw(P4213) -- (P4231);
			\draw[line width=0.5mm,red](P4132) -- (P4312);
			%
			\draw(P3421) -- (P4321);
			\draw(P4231) -- (P4321);
			\draw[line width=0.5mm,green](P4312) -- (P4321);
		\end{tikzpicture}
		\\[.3cm]
		\begin{tikzpicture}[xscale=1, yscale=0.65, color=lightgray]
			\node[blue](P1234) at (0,0){1234};
			%
			\node[blue](P2134) at (-1,1.5){2134};
			\node[blue](P1324) at ( 0,1.5){1324};
			\node[blue](P1243) at ( 1,1.5){1243};
			%
			\node(P2314) at (-2,3){2314};
			\node[blue](P3124) at (-1,3){3124};
			\node[blue](P2143) at ( 0,3){2143};
			\node[blue](P1342) at ( 1,3){1342};
			\node(P1423) at ( 2,3){1423};
			%
			\node[blue](P3214) at (-2.5,4.5){3214};
			\node(P2341) at (-1.5,4.5){2341};
			\node[blue](P3142) at (-0.5,4.5){3142};
			\node(P2413) at ( 0.5,4.5){2413};
			\node(P4123) at ( 1.5,4.5){4123};
			\node[blue](P1432) at ( 2.5,4.5){1432};
			%
			\node(P3241) at (-2,6){3241};
			\node(P2431) at (-1,6){2431};
			\node[blue](P3412) at ( 0,6){3412};
			\node(P4213) at ( 1,6){4213};
			\node(P4132) at ( 2,6){4132};
			%
			\node[blue](P3421) at (-1,7.5){3421};
			\node(P4231) at ( 0,7.5){4231};
			\node[blue](P4312) at ( 1,7.5){4312};
			%
			\node[blue](P4321) at (0,9){4321};
			%
			%
			\draw[line width=0.5mm,blue](P1234) -- (P2134);
			\draw[line width=0.5mm,red](P1234) -- (P1324);
			\draw[line width=0.5mm,green](P1234) -- (P1243);
			%
			\draw(P2134) -- (P2314);
			\draw[line width=0.5mm,green](P2134) -- (P2143);
			\draw[line width=0.5mm,blue](P1324) -- (P3124);
			\draw[line width=0.5mm,green](P1324) -- (P1342);
			\draw(P1243) -- (P2143);
			\draw(P1243) -- (P1423);
			%
			\draw(P2314) -- (P3214);
			\draw(P2314) -- (P2341);
			\draw[line width=0.5mm,red](P3124) -- (P3214);
			\draw[line width=0.5mm,green](P3124) -- (P3142);
			\draw(P2143) -- (P2413);
			\draw(P1342) -- (P3142);
			\draw[line width=0.5mm,red](P1342) -- (P1432);
			\draw(P1423) -- (P4123);
			\draw(P1423) -- (P1432);
			%
			\draw(P3214) -- (P3241);
			\draw(P2341) -- (P3241);
			\draw(P2341) -- (P2431);
			\draw[line width=0.5mm,red](P3142) -- (P3412);
			\draw(P2413) -- (P4213);
			\draw(P2413) -- (P2431);
			\draw(P4123) -- (P4213);
			\draw(P4123) -- (P4132);
			\draw(P1432) -- (P4132);
			%
			\draw(P3241) -- (P3421);
			\draw(P2431) -- (P4231);
			\draw[line width=0.5mm,blue](P3412) -- (P4312);
			\draw[line width=0.5mm,green](P3412) -- (P3421);
			\draw(P4213) -- (P4231);
			\draw(P4132) -- (P4312);
			%
			\draw(P3421) -- (P4321);
			\draw(P4231) -- (P4321);
			\draw[line width=0.5mm,green](P4312) -- (P4321);
		\end{tikzpicture}
	\end{minipage}
}
{
As in \cref{subsec:trees}, we can define natural generating trees for the $(U,D)$-permutree minimal permutations.
Namely, fix an arbitrary priority order~$\prec$ on~$\{s_1, \dots, s_{n-1}\}$.
For an $(U,D)$-permutree minimal permutation~$\pi$, we denote by~$\pi(U, D, \prec)$ the $\prec$-lexicographic minimal reduced word for~$\pi$ that is accepted by~$\automatonP(U,D)$.
We denote by~$\lexmin(n, U, D, \prec)$ the set of reduced words of the form~$\pi(U, D, \prec)$ for all $(U,D)$-permutree minimal permutations~$\pi \in \fS_n$.
As in \cref{prop:generatingTrees}, $\lexmin(n, U, D, \prec)$ is closed by prefix.
This yields a natural generating tree on~$\lexmin(n, U, D, \prec)$ where the parent of a reduced word~$w$ is obtained by deleting its last letter.
Replacing each reduced word by the corresponding permutation, this provides a generating tree for the $(U,D)$-permutree minimal permutations of~$\fS_n$.
We have represented this tree on the right for~$(U,D) = (\{2,3\}, \varnothing)$ (top) and~$(\{2\},\{3\})$ (bottom) and the priority order~$s_1 \prec s_2 \prec s_3$.
As in \cref{subsec:trees}, these trees are drawn on top of the Hasse diagram of the right weak order on permutations and the edges are colored according to the simple transpositions.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Permutree sorting versus Coxeter sorting}\label{sec:coxeterSortable}

In this section, we discuss the particular case when~$U$ and~$D$ partition~${\{2, \dots, n-1\}}$.
In that situation, we connect the $(U,D)$-permutree sorting with the $c$-sorting of~\cite{Reading-sortableElements}.

We consider a \defn{Coxeter element}~$c$ of~$\fS_n$, \ie the product of all simple transpositions $\{s_1, \dots, s_{n-1}\}$ in an arbitrary order.
For a permutation $\pi \in \fS_n$, the \defn{$c$-sorting word} $\pi(c)$ is the lexicographically smallest reduced word for $\pi$ in the infinite word $c^\infty = c \cdot c \cdot c \cdot c \cdots$.
%Note that strictly speaking, $\pi(c)$ depends on a reduced word for~$c$, not only on the Coxeter element~$c$.
%Here, we assume that we have chosen a reduced word and hide this dependence.
We let~$I_1, \dots, I_p$ denote the subsets of~$[n-1]$ such that~$\pi(c) = c_{I_1} \cdot c_{I_2} \cdots c_{I_p}$ where~$c_I$ is the subword of~$c$ obtained by keeping only the letters~$s_i$ for~$i \in I$.
The permutation $\pi$ is \defn{$c$-sortable} if~$I_1 \supseteq I_2 \supseteq \dots \supseteq I_p$.
%Note that this does not depend on the choice of the reduced word~$c$, only on the Coxeter element~$c$.

A Coxeter element~$c$ of~$\fS_n$ defines a partition ${\{2, \dots, n-1\} = U_c \sqcup D_c}$, where~$U_c$ (resp.~$D_c$) consists of the elements~$j \in \{2, \dots, n-1\}$ such that~$s_j$ appears before (resp.~after) $s_{j-1}$ in~$c$.
For instance, when~$c = s_2 \cdot s_5 \cdot s_4 \cdot s_3 \cdot s_1 \cdot s_6$, we obtain~$U_c = \{2,4,5\}$ and~$D_c = \{3,6\}$.
Said differently, $j \in U$ (resp.~$j \in D$) if~$c$ is accepted by~$\automatonU(j)$ but not by~$\automatonD(j)$ (resp.~by~$\automatonD(j)$ but not by~$\automatonU(j)$).
The $c$-sorting of~\cite{Reading-sortableElements} and the $(U_c, D_c)$-permutree sorting are connected as follows.

\begin{theorem}
\label{thm:csorting}
The following are equivalent for any Coxeter element~$c$ and any permutation~$\pi$:
\begin{compactenum}[(i)]
	\item $\pi$ is $c$-sortable,
	\item the $c$-sorting word~$\pi(c)$ is accepted by the automaton~$\automatonP(U_c, D_c)$,
	\item there exists a reduced word for~$\pi$ accepted by the automaton~$\automatonP(U_c, D_c)$,
	\item for each~$j \in \{2, \dots, n-1\}$, there exists a reduced word for $\pi$ that is accepted by the automaton~$\automatonU(j)$ if~$j \in U_c$ and~$\automatonD(j)$ if~$j \in D_c$,
	\item $\pi$ avoids $jki$ for~$j \in U_c$ and $kij$ for~$j \in D_c$.
\end{compactenum}
\end{theorem}

We conclude this section with three negative observations and warnings about the connection between $c$-sorting and $(U_c,D_c)$-permutree sorting.

\begin{remark}
Even if a permutation~$\pi$ avoids~$jki$ (resp.~$kij$) for a given~$j$, there might be no Coxeter element~$c$ for which $\pi$ is $c$-sortable and~$j \in U_c$ (resp.~$j \in D_c$).
For instance, $41325$ avoids $2ki$ and~$ki4$, but contains~$352$ and~$413$, so it is not $c$-sortable for any Coxeter element~$c$.
\end{remark}

\begin{remark}
When a permutation~$\pi$ is not $c$-sortable, there might exist~$j \in U_c$ (resp.~$j \in D_c$) for which the $c$-sorting word~$\pi(c)$ is not accepted by~$\automatonU(j)$ (resp.~$\automatonD(j)$) even if~$\pi$ avoids~$jki$ (resp.~$kij$).
For instance, consider~$c = s_2 \cdot s_1 \cdot s_3$ and~$\pi = 4213 = s_3 \cdot s_1 \cdot s_2 \cdot s_1 =  s_3 \cdot s_2 \cdot s_1 \cdot s_2 =  s_1 \cdot s_3 \cdot s_2 \cdot s_1$.
Then~$2 \in U_c$, and the $c$-sorting word~$\pi(c) = s_1 \cdot s_3 \cdot s_2 \cdot s_1$ is rejected by~$\automatonU(2)$ while~$\pi$ contains no~$2ki$ (and indeed~$s_3 \cdot s_2 \cdot s_1 \cdot s_2$ is accepted by~$\automatonU(2)$).
\end{remark}

\begin{remark}
Given a Coxeter element $c$, the word $c^\infty$ which is used to compute $\pi(c)$ is a \defn{sorting network}. This means that we decide \emph{beforehand} a list of transpositions to apply if appropriate. On the other hand, the permutree sorting given in \cref{algo:permutreeSorting} is \emph{not} a sorting network. Indeed, the order on transpositions depends on the permutation and more specifically on the state of the automaton we are at. A natural question then occurs: can we replace the permutree sorting algorithm by a sorting network? Or said differently, when~$U$ and~$D$ are disjoint but do not cover~$\{2, \dots, n-1\}$, can we find a word $\tilde{c}$ which plays the role of $c^\infty$ in the sense that looking at $\pi(\tilde{c})$ would be enough to check whether $\pi$ is accepted by $\automatonP(U,D)$?
%
The answer is negative in general. A counter-example is found for $n = 5$, $U = \{ 2\}$, and $D=\{ 4 \}$. In this case one can check through computer exploration that no reduced word $\tilde{c}$ of the maximal permutation $54321$ can be used as a sorting network. 
% Namely, for all choices of $\tilde{c}$, there exist a permutation $\pi$ which is accepted by $\automatonP(U,D)$ whereas the reduced word $\pi(\tilde{c})$ is rejected. %The healthy states of $\automatonP(\{ 2\},\{ 4 \})$ are shown in \cref{fig:automataProduct}. We see that accepted reduced words can start with either $s_2$ or $s_3$. For some permutations, such as $54213$ shown in \cref{exm:algo2}, all accepted reduced words start with $s_3$ whereas for some other permutations such as $35421$, all accepted reduced words start with $s_2$. This eventually leads to an empty intersection for the choice of $\tilde{c}$.

%Nevertheless, it seems interesting to study in which case the answer is positive. The Cambrien case with the $c$-sorting word when $U$ and~$D$ form a partition of~$\{2, \dots, n-1\}$ is one example. The case where $|U| + |D| = 1$ is another one. This is the case corresponding to \cref{thm:patternAvoidance} where we have only one automaton. In this case, we can construct a word $\tilde{c}$ by reading the healthy states of the automaton linearly, adding at each state the word $(s_{i_1} \cdots s_{i_k})^k s_j$ where $s_{i_1}, \dots, s_{i_k}$ are the looping transitions and $s_j$ is the transition going to the next healthy state. This process gives a prefix that can be extended in any way to obtain a proper sorting word $\tilde{c}$. For example, if $U = \{2\}$, we obtain the prefix $s_3 \cdot s_2 \cdot s_1 \cdot s_3$ and indeed $s_3 \cdot s_2 \cdot s_1 \cdot s_3 \cdot s_2 \cdot s_1$ acts as a sorting network equivalent to the $(\{2\},\varnothing)$-permutree sorting. %This process actually seems to extend to all cases where, at each healthy state of the intersection automaton, the choices for the healthy transitions commute. For example, in the case where $n=5$, $U = \{ 4 \}$ and $D = \{ 2 \}$ as illustrated in \cref{fig:automataProduct}, the word $s_1 \cdot s_2 \cdot s_4 \cdot s_3 \cdot s_2 \cdot s_1 \cdot s_4 \cdot s_3 \cdot s_2$ gives a proper sorting network. 
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Extensions to finite Coxeter groups}\label{sec:Coxeter}

In this section we present possible extensions of our results to other finite Coxeter groups. Remember that the $c$-sorting algorithm defined by Reading~\cite{Reading-CambrianLattices} works in all types and defines the Cambrian lattices as certain lattice quotients of the weak order. On the other hand, there is no definition of permutrees~\cite{PilaudPons-permutrees} beyond type $A$. The present work can be used as a first step towards defining and studying such objects. 

A Coxeter group is generated by a family $(s_i)_{i \in [n]}$ such that $s_i^2 = 1$ and $(s_i s_j)^{m_{i,j}} = 1$ for certain coefficients $m_{i,j}$ with $2 \leq m_{i,j} \leq \infty$ when $i \neq j$. In particular, this defines the Coxeter graph whose vertices are the $s_i$ and edges are the pairs~$(s_i, s_j)$ with~$m_{i,j} > 2$. A Coxeter element $c$ of a finite Coxeter group $W$ defines an orientation of the Coxeter graph of $W$: we orient the edge from $s_i$ to $s_j$ if $s_i$ appears before $s_j$ in $c$ and reciprocally. Each orientation defines a certain lattice congruence of the weak order: it is the smallest lattice congruence such that $s_j \equiv s_j s_i \equiv \dots \equiv s_j s_i s_j \dots$ where the last element is of length $m_{i,j} - 1$. The $c$-sortable elements are the weak order minimal elements of the congruence classes. See~\cite{Reading-latticeCongruences} for more details. 

% A Coxeter element gives a full orientation of the Coxeter graph. 
By allowing each edge of the Coxeter graph to be either non-oriented, right, left or with both orientations, we define some new lattice congruences which we call the \defn{permutree congruences}. In type $A$, the Coxeter graph is a line ($s_j$ is connected to $s_{j-1}$ and $s_{j+1}$) and the orientation is then entirely determined by our two sets $U$ and $D$: $j\in U$ (resp. $j\in D$) means we orient the edge $(s_j, s_{j-1})$ from $s_j$ to $s_{j-1}$ (resp. $s_{j-1}$ to $s_j$). The case where $U = \varnothing$ and~$D = \{j\}$ or the opposite corresponds to choosing one edge and orient it. Then the automaton $\automatonD(j)$ is actually constructed recursively by following a certain path in the graph from the oriented edge (in type $A$, this means decreasing $j$). We conjecture that this principle can be somehow generalized to other types and give two examples in type $B$ and $D$.


%In this section we present possible extensions of our results to other types of Coxeter groups. As permutations will be not be at our disposal for all Coxeter group, we propose an alternative method tha appears to allow a similar definition of our automata with the sole need of looking at orientations of the Coxeter graph of the group in question. In type A this connection can be readily seen via a bijection between $j\in U$ (resp. $j\in D$) and the orientation from $j$ to $j-1$ (resp. $j-1$ to $j$) in the Coxeter graph of type A. This in turn implies that our automata can be constructed by following a path in the Coxeter graph. That is, to construct $\automatonU(j)$ we take the path starting at vertex $j-1$ and walk upwards the graph, adding healthy transitions by noticing which vertices we have visited and ill and dead transitions accordingly. 

%In other types we conjecture that our automata can be adapted following this line of thinking and 2 rules based if the Coxeter group is simply-laced or not. In the simply-laced case, if the path in the Coxeter graph has branching nodes such as in types D or E, our automata is divided into the amount of branches so that each automaton represents a straight path containing each particular branch. In the non simply-laced case, where we have edges with labels $l\in\{4,5\}$ such as in types $B$ and $H$, if the path encounters such an edge, it is bounced back and must return backwards. This bouncing fenomenon applies to the automaton as well. Figures \ref{fig:automataBRecursive} and \ref{fig:automatonDOrientation} respectively present constructions and examples of their corresponding cases.

\subsection{Type B}

\begin{figure}[b]
	\centerline{
		$\automatonU(j) =$ \hspace{-.7cm}
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=1cm, on grid, auto, baseline=-1.4cm]
			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.3cm of q_0] {}; 
			\node[state,minimum size=0.5cm] (q_2) [below= 1.3cm of q_1] {}; 
			\node (q_3) [right= 2cm of q_0] {$\automatonU(j+1)$};
			\path[->] 
			(q_0) edge node [swap] {$s_{j-1}$} (q_1)
			edge node {$s_j$} (q_3)
			(q_1) edge node [swap] {$s_j$} (q_2);
		\end{tikzpicture}
		\,
		$\automatonU(n) =$ \hspace{-.7cm}
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=1cm, on grid, auto, baseline=-1.4cm]
			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.3cm of q_0] {}; 
			\node[state,minimum size=0.5cm] (q_2) [below= 1.3cm of q_1] {}; 
			\node (q_3) [right= 2cm of q_0] {$\automatonD(n)$};
			\path[->] 
			(q_0) edge node [swap] {$s_{n-1}$} (q_1)
			edge node {$s_n$} (q_3)
			(q_1) edge node [swap] {$s_n$} (q_2);
		\end{tikzpicture}
		\,
		$\automatonD(j) =$ \hspace{-.7cm}
		\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto, baseline=-1.4cm] 
			\node[state,initial,accepting,minimum size=0.5cm] (q_0) {}; 
			\node[state,accepting,minimum size=0.5cm] (q_1) [below= 1.3cm of q_0] {}; 
			\node[state,minimum size=0.5cm] (q_2) [below= 1.3cm of q_1] {}; 
			\node (q_3) [right= 2 cm of q_0] {$\automatonD(j-1)$};
			\path[->] 
			(q_0) edge node [swap] {$s_{j}$} (q_1)
			edge node {$s_{j-1}$} (q_3)
			(q_1) edge node [swap] {$s_{j-1}$} (q_2);
		\end{tikzpicture}
	}
	\caption{Recursive definition of the automata $\automatonU(j)$ and $\automatonD(j)$ in type B.}
	\label{fig:automataBRecursive}
\end{figure}

The Coxeter graph of type $B$ is similar to the one of type $A$ with the exception that $m_{n-1,n} = 4$ (whereas $m_{n-1,n} = 3$ in type $A$). We claim that the automata $\automatonD(j)$ and $\automatonU(j)$ can be recursively constructed following Figure~\ref{fig:automataBRecursive}. The idea is to ``unfold'' the edge $(s_{n-1},s_n)$ and use the type $A$ construction on a linear graph $s_1, \dots, s_n, s_{n-1}, s_n, \dots, s_1$. Notice that $\automatonD(j)$ has not been altered while $\automatonU(j)$ is virtually as before except for when $j=n$ where it is now connected to $\automatonD(n)$ as if it was ``bouncing back''. These automata capture completely the sorting process of type $B$ permutations. It can also be checked for small sizes that they indeed select the right elements in the lattice. In particular, the case where $U\sqcup D = \{2,\ldots,n\}$ gives $\binom{2n}{n}$ permutree sortable permutations, \emph{i.e.} the $B$-Catalan numbers as expected from the Cambrian case.

%In the particular case of type B we have a general rule that works for all $n$ as presented in Figure \ref{fig:automataBRecursive}. Notice that $\automatonD(j)$ has not been altered. This aligns with the fact that paths stemming out from $j$ downwards in type B are equivalent to those in type A. Meanwhile, $\automatonU(j)$ is virtually as before except for when $j=n$ where it is now connected to $\automatonD(n)$. This represents the notion that paths stemming from $j-1$ upwards encounter the last edge labeled with a 4 and thus must be bounced back. These automata capture completely the sorting process and coincide with the fact that a complete disjoint union of $\{2,\ldots,n\}=U\sqcup D$ leaves us with a total amount of ${\mleft(\genfrac..{0pt}{}{2n}{n}\mright)}$ elements recognized by all the corresponding automata. That is, the $B$-Catalan number which is expected as it did in the Cambrian case.

\subsection{Type D}

Type $D$ is an example of a simply-laced case, meaning that $m_{i,j} \leq 3$ for all $i$ and $j$. In this case, we see a ``branching'' phenomenon and it appears that a single oriented edge leads to multiple automata which need to be intersected and follow a more technical construction than for type $A$. As of yet, we know no general construction but we show in Figure~\ref{fig:automatonDOrientation} a working example (checked by computer exploration) for the case $D_4$.

%For type D we conjecture that we can modify our automata by following paths of the Coxeter graph and interpreting branching paths as a need to define and intersect more automata. That is, the automata $\automatonU(j)$ and $\automatonD(j)$ will now be formed by intersections of other automata. This method works for a subset of all possible orientations, in particular those that are oriented from the extremes of the graph inwards. Figure \ref{fig:automatonDOrientation} presents such an example.

\begin{figure}[h!]
	\setlength{\belowcaptionskip}{-30pt}
	\centerline{
		\scalebox{.9}{
			\begin{tabular}{c@{\quad}c@{\quad}c@{\qquad}c}
				$D_4$ oriented &
				$\automatonU(j)_1$ &
				$\automatonU(j)_2$
				\\[.1cm]
				\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        
				\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
				%uncomment if require: \path (0,185); %set diagram left start at 0, and has height of 185
				%Shape: Ellipse [id:dp226657005163861] 
				\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (100.21,128) .. controls (100.21,125.27) and (102.8,123.05) .. (106,123.05) .. controls (109.2,123.05) and (111.79,125.27) .. (111.79,128) .. controls (111.79,130.73) and (109.2,132.95) .. (106,132.95) .. controls (102.8,132.95) and (100.21,130.73) .. (100.21,128) -- cycle ;
				%Shape: Ellipse [id:dp33383604396421096] 
				\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]  (100.21,50) .. controls (100.21,47.27) and (102.8,45.05) .. (106,45.05) .. controls (109.2,45.05) and (111.79,47.27) .. (111.79,50) .. controls (111.79,52.73) and (109.2,54.95) .. (106,54.95) .. controls (102.8,54.95) and (100.21,52.73) .. (100.21,50) -- cycle ;
				%Shape: Ellipse [id:dp6264675627761336] 
				\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]  (10.59,87.5) .. controls (10.59,84.77) and (13.18,82.56) .. (16.38,82.56) .. controls (19.57,82.56) and (22.16,84.77) .. (22.16,87.5) .. controls (22.16,90.24) and (19.57,92.45) .. (16.38,92.45) .. controls (13.18,92.45) and (10.59,90.24) .. (10.59,87.5) -- cycle ;
				%Shape: Ellipse [id:dp3651254961419923] 
				\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]  (63.19,87.5) .. controls (63.19,84.77) and (65.78,82.56) .. (68.98,82.56) .. controls (72.17,82.56) and (74.77,84.77) .. (74.77,87.5) .. controls (74.77,90.24) and (72.17,92.45) .. (68.98,92.45) .. controls (65.78,92.45) and (63.19,90.24) .. (63.19,87.5) -- cycle ;
				%Straight Lines [id:da7807071493413082] 
				\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]    (68.98,87.5) -- (106,128) ;
				%Straight Lines [id:da7309554765749118] 
				\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]    (68.98,87.5) -- (16.38,87.5) ;
				%Straight Lines [id:da05459000277103243] 
				\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]    (106,50) -- (68.98,87.5) ;
				%Straight Lines [id:da855858893257617] 
				\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.75]    (63.19,87.5) -- (16.38,87.5) ;
				\draw [shift={(39.78,87.5)}, rotate = 360] [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle    ;
				% Text Node
				\draw (9.03,96.64) node [anchor=north west][inner sep=0.75pt]    {$1$};
				% Text Node
				\draw (99.2,136.41) node [anchor=north west][inner sep=0.75pt]    {$4$};
				% Text Node
				\draw (99.72,58.78) node [anchor=north west][inner sep=0.75pt]    {$3$};
				% Text Node
				\draw (62.43,95.44) node [anchor=north west][inner sep=0.75pt]    {$2$};
				\end{tikzpicture}
				&
				\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto]
				\node[state,initial,accepting,minimum size=0.5cm] (h1)   {}; 
				\node[state,accepting,minimum size=0.5cm] (i1) [below= 1.3cm of h1] {}; 
				\node[state,minimum size=0.5cm] (d1) [below= 1.3cm of i1] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h2) [right= 1.3cm of h1] {};
				\node[state,accepting,minimum size=0.5cm] (i2) [below= 1.3cm of h2] {}; 
				\node[state,minimum size=0.5cm] (d2) [below= 1.3cm of i2] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h3) [right= 1.3cm of h2] {};
				%
				\node[state,accepting,minimum size=0.5cm] (h4) [right= 1.3cm of h3] {};
				\node[state,accepting,minimum size=0.5cm] (i4) [below= 1.3cm of h4] {}; 
				\node[state,minimum size=0.5cm] (d4) [below= 1.3cm of i4] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h5) [right= 1.3cm of h4] {};
				\node[state,accepting,minimum size=0.5cm] (i5) [below= 1.3cm of h5] {}; 
				\path[->] 
				(h1) edge node {$s_2$} (h2)
				edge node [swap] {$s_1$} (i1)
				(i1) edge node [swap] {$s_2$} (d1)
				%
				(h2) edge node {$s_3$} (h3)
				edge node [swap] {$s_2$} (i2)
				(i2) edge node [swap] {$s_3$} (d2)
				%
				(h3) edge node {$s_2$} (h4)
				%
				(h4) edge node {$s_1$} (h5)
				edge node [swap] {$s_2$} (i4)
				(i4) edge node [swap] {$s_1$} (d4)
				%
				(h5) edge node [swap] {$s_1$} (i5);
				\end{tikzpicture}
				&
				\begin{tikzpicture}[scale=.8, shorten >=1pt, node distance=2cm, on grid, auto]
				\node[state,initial,accepting,minimum size=0.5cm] (h1)   {}; 
				\node[state,accepting,minimum size=0.5cm] (i1) [below= 1.3cm of h1] {}; 
				\node[state,minimum size=0.5cm] (d1) [below= 1.3cm of i1] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h2) [right= 1.3cm of h1] {};
				\node[state,accepting,minimum size=0.5cm] (i2) [below= 1.3cm of h2] {}; 
				\node[state,minimum size=0.5cm] (d2) [below= 1.3cm of i2] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h3) [right= 1.3cm of h2] {};
				%
				\node[state,accepting,minimum size=0.5cm] (h4) [right= 1.3cm of h3] {};
				\node[state,accepting,minimum size=0.5cm] (i4) [below= 1.3cm of h4] {}; 
				\node[state,minimum size=0.5cm] (d4) [below= 1.3cm of i4] {}; 
				%
				\node[state,accepting,minimum size=0.5cm] (h5) [right= 1.3cm of h4] {};
				\node[state,accepting,minimum size=0.5cm] (i5) [below= 1.3cm of h5] {}; 
				\path[->] 
				(h1) edge node {$s_2$} (h2)
				edge node [swap] {$s_1$} (i1)
				(i1) edge node [swap] {$s_2$} (d1)
				%
				(h2) edge node {$s_4$} (h3)
				edge node [swap] {$s_2$} (i2)
				(i2) edge node [swap] {$s_4$} (d2)
				%
				(h3) edge node {$s_2$} (h4)
				%
				(h4) edge node {$s_1$} (h5)
				edge node [swap] {$s_2$} (i4)
				(i4) edge node [swap] {$s_1$} (d4)
				%
				(h5) edge node [swap] {$s_1$} (i5);
				\end{tikzpicture}
			\end{tabular}
		}
	}
	\caption{A partial orientation of $D_4$ and the corresponding automata that form $\automatonU(2)$.}
	\label{fig:automatonDOrientation}
\end{figure}
 

%\acknowledgements{}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
