\chapter{Préliminaires}

\begin{note}
Sauf indication contraire, on suppose dans le texte qu'une fonction est toujours définie sur l'entièreté de son domaine (i.e. c'est une application).
\end{note}

\begin{note}
Sauf indication contraire, on suppose dans le texte qu'une fonction est $\N \to \N$, avec $\N = \setThree{1}{2}{\dots}$.
\end{note}

\begin{defn}
L'ensemble $\range{n}$ est $\setFour{1}{2}{\dots}{n}$.
\end{defn}

\section{Structures Discrètes}

On rappelle plusieurs notions de bases, qu'on peut trouver, par exemple, dans \cite[Chapitre~7]{R02}.

\begin{note}
Soit $G = \tuplTwo{S}{A}$ un graphe \resp{orienté}{non-orienté}, alors $S$ est son ensemble de sommets et $A$ est l'ensemble des \resp{arcs}{arêtes} tel que \resp{$\tuplTwo{s_i}{s_j}$ indique un arc du sommet $s_i$ au sommet $s_j$}{$\setTwo{s_i}{s_j}$ indique une arête entre les sommets $s_i$ et $s_j$} avec $s_i \neq s_j$.
\end{note}

\begin{defn}
Soit $G = \tuplTwo{S}{A}$ un graphe \resp{orienté}{non-orienté}, \resp{un \defin{chemin}}{une \defin{chaîne}} de $s_0$ à $s_n$ dans $G$ est une suite finie d'\resp{arcs $\lstFour{a_1 = \tuplTwo{s_0}{s_1}}{a_2 = \tuplTwo{s_1}{s_2}}{\dots}{a_n = \tuplTwo{s_{n-1}}{s_n}}$}{arêtes $\lstFour{a_1 = \setTwo{s_0}{s_1}}{a_2 = \setTwo{s_1}{s_2}}{\dots}{a_n = \setTwo{s_{n-1}}{s_n}}$}. Lorsque les \resp{arcs}{arêtes} $\lstFour{a_1}{a_2}{\dots}{a_n}$ sont distincts, \resp{le chemin}{la chaîne} est \defin{simple}.
\end{defn}

\begin{note}
Sauf indication contraire, on suppose par la suite qu'\resp{un chemin}{une chaîne} est simple.
\end{note}

\begin{defn}
Soit $G = \tuplTwo{S}{A}$ un graphe \resp{orienté}{non-orienté} et \resp{un chemin}{une chaîne} sur les sommets $\lstFour{s_0}{s_1}{\dots}{s_n}$. \resp{Le chemin}{la chaîne} est un \resp{\defin{circuit}}{\defin{cycle}} si $s_0 = s_n$.
\end{defn}

\begin{defn}\label{defn-graph-hampath}
Soit $G = \tuplTwo{S}{A}$ un graphe \resp{orienté}{non-orienté} et $C$ \resp{un chemin}{une chaîne} qui passe par tous les sommets (i.e. $\forall s \in S, \exists a \in A$ tel que $s \in a$), alors $C$ est \defin{hamiltonien}\srespOne{ne}.
\end{defn}

\begin{defn}
Soit $G = \tuplTwo{S}{A}$ un graphe orienté, le \defin{demi-degré} \resp{intérieur}{extérieur} d'un sommet $s \in S$ est \resp{$\indeg{s}$}{$\outdeg{s}$} le nombre d'arcs qui ont $s$ comme \resp{destination}{source}, c'est-à-dire \resp{$\cardnSet{\setcond{\tuplTwo{s_i}{s_j} \in A}{s_j = s}}$}{$\cardnSet{\setcond{\tuplTwo{s_i}{s_j} \in A}{s_i = s}}$}. Le \defin{degré} d'un sommet $s \in S$ est $\fulldeg{s} = \indeg{s} + \outdeg{s}$.
\end{defn}

\begin{defn}\cite[Chapitre~9]{J17}
Une \defin{arborescence} est un couple $T = \tuplTwo{G}{s_0}$ où $G = \tuplTwo{S}{A}$ est un arbre (graphe non-orienté connexe et acyclique) et $s_0 \in S$ est la racine. Soit une chaîne sur les sommets $\lstFour{s_0}{s_1}{\dots}{s_n}$, plusieurs définitions suivent:
\begin{itemize}
\item $i$ est la \defin{profondeur} $\fofOne{p}{s_i}$ du sommet $s_i$.
\item La \defin{hauteur} $\fofOne{h}{T}$ est la profondeur maximale d'un de ses sommets.
\item $s_{i-1}$ est le \defin{parent} de $s_i$.
\item Si $s$ est le parent de $s'$, alors $s'$ est un \defin{enfant} de $s$.
\item $\lstFour{s_0}{s_1}{\dots}{s_{i-1}}$ sont les \defin{ancêtres} de $s_i$.
\item Si $s$ est l'un des ancêtres de $s'$, alors $s'$ est l'un des \defin{descendants} de $s$.
\item Si $s$ n'a pas d'enfants, alors c'est une \defin{feuille}, sinon c'est un sommet \defin{interne}.
\item La \defin{sous-arborescence} de $T$ de racine $s'$ est l'arborescence $T' = \tuplTwo{G'}{s'}$ telle que $G'$ est le sous-graphe de $G$ qui contient $s'$ et tous ses descendants.
\end{itemize}
\end{defn}

\begin{defn}\cite[Chapitre~9]{J17}
Une arborescence est \defin{binaire} si chaque sommet a au plus deux enfants et si on précise, pour chaque enfant, si c'est l'enfant gauche ou droit. En plus, une arborescence binaire est \defin{entière} si chaque sommet interne a exactement deux enfants.
\end{defn}

\section{Machines de Turing}

On rappelle plusieurs notions de bases, qu'on peut trouver, par exemple, dans \cite{P14}.

\begin{defn}
$M = \tupl{\Sigma}{\Gamma}{B}{Q}{q_0}{q_a}{q_r}{\delta}$ est une \gls{mTd} à $k \geq 2$ rubans où:
\begin{itemize}
\item $\Sigma$ est l'alphabet d'entrée, un ensemble fini non vide
\item $\Gamma$ est l'alphabet de travail, un ensemble fini tel que $\Sigma \subset \Gamma$
\item $B \in \Gamma \setminus \Sigma$ est le symbol blanc
\item $Q$ est l'ensemble d'états, un ensemble fini
\item $q_0 \in Q$ est l'état initial
\item $\lstTwo{q_a}{q_r} \in Q$ sont des états terminaux (respectivement d'acceptation et de refus)
\item $\delta : \paren{Q \setminus \setTwo{q_a}{q_r}} \times \Gamma^{k-1} \to Q \times \Gamma^{k-1} \times \setThree{\mathrm{G}}{\mathrm{S}}{\mathrm{D}}^k$ est la fonction de transition
\end{itemize}
$\fofOne{L}{M}$ est le langage de $M$, l'ensemble des mots sur lesquels $M$ s'arrête dans l'état d'acceptation. Pour $x \in \Sigma^*$ un mot sur lequel $M$ s'arrête, $\fof{M}{x} \in \Gamma^*$ est le mot écrit sur le ruban de sortie lorsque $M$ s'arrête.
\end{defn}

\begin{defn}
$N = \tupl{\Sigma}{\Gamma}{B}{Q}{q_0}{q_a}{q_r}{\delta}$ est une \gls{mTnd} à $k \geq 2$ rubans où la seule différence avec une \gls{mTd} est:
\begin{itemize}
\item $\delta : \paren{Q \setminus \setTwo{q_a}{q_r}} \times \Gamma^{k-1} \to \power{Q \times \Gamma^{k-1} \times \setThree{\mathrm{G}}{\mathrm{S}}{\mathrm{D}}^k}$ est la relation de transition
\end{itemize}
$\fofOne{L}{N}$ est le langage de $N$, l'ensemble des mots sur lesquels il existe un choix de transitions tels que $N$ s'arrête dans l'état d'acceptation.
\end{defn}

\begin{note}
Sauf indication contraire, on suppose dans le texte qu'une \gls{mT} est déterministe, a $k = 3$ rubans et s'arrête sur toutes ses entrées (peu importe le choix des transitions, s'il y a lieu).
\end{note}

\begin{defn}
Soit $f$ une fonction, alors \resp{$\DTime{f}$}{$\DSpace{f}$} est l'ensemble des langages décidés par une \gls{mT} $M$ telle que $\exists \alpha \in \N, \forall x \in \Sigma^*$, $M$ sur $x$ \resp{fonctionne en temps au plus $\alpha \fofOne{f}{\len{x}}$}{utilise au plus $\alpha \fofOne{f}{\len{x}}$ espace sur chaque ruban de travail}.

Si $F$ est un ensemble de fonctions, alors \resp{$\DTime{F}$ est $\displaystyle\bigcup_{f \in F}\DTime{f}$}{$\DSpace{F}$ est $\displaystyle\bigcup_{f \in F} \DSpace{f}$}.
\end{defn}

\begin{defn}
Soit $f$ une fonction, alors \resp{$\NTime{f}$}{$\NSpace{f}$} est l'ensemble des langages décidés par une \gls{mTnd} $N$ telle que $\exists \alpha \in \N, \forall x \in \Sigma^*$, $N$ sur $x$ \resp{fonctionne en temps au plus $\alpha \fofOne{f}{\len{x}}$}{utilise au plus $\alpha \fofOne{f}{\len{x}}$ espace sur chaque ruban de travail} peu importe le choix de transitions.

Si $F$ est un ensemble de fonctions, alors \resp{$\NTime{F}$ est $\displaystyle\bigcup_{f \in F}\NTime{f}$}{$\NSpace{F}$ est $\displaystyle\bigcup_{f \in F}\NSpace{f}$}.
\end{defn}

\begin{defn}
On note quelques classes de complexités utiles: $\NPClass = \NTime{n^{\bigO{1}}}$, $\PClass = \DTime{n^{\bigO{1}}}$, $\LClass = \DSpace{\bigO{\fofOne{\log}{n}}}$ et $\NLClass = \NSpace{\bigO{\fofOne{\log}{n}}}$.
\end{defn}

\begin{defn}
Soit $\Sigma$ et $\Gamma$ des alphabets, $A \subseteq \Sigma^*$ et $B \subseteq \Gamma^*$ des langages et $M$ une \gls{mTd} avec alphabets d'entrée $\Sigma$ et de travail $\Gamma$ telle que $\forall x \in \Sigma^*, x \in A \iff \fofOne{M}{x} \in B$, alors $A$ \defin{se réduit à} $B$, via la réduction $M$, qu'on note aussi $A \reducBottom{M} B$.
\end{defn}

\begin{defn}
$A \reducLog B$ indique que $\exists M$ une \gls{mTd} telle que $A \reducBottom{M} B$ et $\exists \alpha \in \N, \forall x \in \Sigma^*$, $M$ sur $x$ utilise au plus $\alpha \fofOne{\log}{\len{x}}$ espace sur chaque ruban de travail.
\end{defn}

\begin{defn}
Soit $A$ un langage, $\mathscr{C}$ un ensemble de langages et $\reducBottom{M}$ une réduction alors $A \in \Hard{\mathscr{C}}$ selon $\reducBottom{M}$ si $\forall B \in \mathscr{C}$, $B \reducBottom{M} A$. Si, en plus, $A \in \mathscr{C}$ alors $A \in \Complete{\mathscr{C}}$ selon $\reducBottom{M}$.
\end{defn}

\begin{defn}
Soit $\mathscr{C}$ un ensemble de langages, alors $\Co{\mathscr{C}}$ est l'ensemble $\setcond{A}{\setnot{A} \in \mathscr{C}}$.
\end{defn}

\section{Automates à Pile}

On rappelle plusieurs notions de bases, qu'on peut trouver, par exemple, dans \cite{Si12}.

\begin{defn}
$A = \tupl{\Sigma}{\Pi}{Z_0}{Q}{q_0}{q_a}{\delta}$ est un \gls{PDA} où:
\begin{itemize}
\item $\Sigma$ est l'alphabet d'entrée, un ensemble fini non vide
\item $\Pi$ est l'alphabet de pile, un ensemble fini
\item $Z_0 \in \Pi \setminus \Sigma$ est le symbole initial de pile
\item $Q$ est l'ensemble d'états, un ensemble fini
\item $q_0 \in Q$ est l'état initial
\item $q_a \in Q$ est l'état d'acceptation
\item $\delta : Q \times \paren{\Sigma \cup \setOne{\varepsilon}} \times \Pi \to \power{Q \times \paren{\Pi \cup \setOne{\varepsilon}}}$ est la relation de transition
\end{itemize}
$\fofOne{L}{A}$ est le langage de $A$, l'ensemble des mots sur lesquels il existe un choix de transitions tels que $A$ se déplace uniquement de gauche à droite et s'arrête dans l'état d'acceptation.
\end{defn}

\begin{defn}
$A = \tupl{\Sigma}{\Pi}{Z_0}{Q}{q_0}{q_a}{\delta}$ est un \gls{DPDA} où la seule différence avec un \gls{PDA} est:
\begin{itemize}
\item $\delta : Q \times \paren{\Sigma \cup \setOne{\varepsilon}} \times \Pi \to Q \times \paren{\Pi \cup \setOne{\varepsilon}}$ est la fonction de transition
\item $\forall q \in Q, Z \in \Pi$, si $\exists a \in \Sigma : \fofThree{\delta}{q}{a}{Z} \neq \emptyset$ alors $\fofThree{\delta}{q}{\varepsilon}{Z} = \emptyset$
\end{itemize}
$\fofOne{L}{A}$ est le langage de $A$, l'ensemble des mots sur lesquels $A$ se déplace uniquement de gauche à droite et s'arrête dans l'état d'acceptation.
\end{defn}

\begin{defn}
\resp{$\CFL$}{$\DCFL$} est l'ensemble des langages décidés par un \resp{\gls{PDA}}{\gls{DPDA}}.
\end{defn}

\begin{defn}\cite{S78}\cite{Y23}
\resp{$\LogCFL$}{$\LogDCFL$} est l'ensemble des langages $A$ tel que $A \reducLog B \in$ \resp{$\CFL$}{$\DCFL$}.
\end{defn}

%\begin{defn}\cite{S78}
%Soit $\mathscr{C}$ un ensemble de langages, alors $\LOG{\mathscr{C}}$ est l'ensemble $\setcond{A}{A \reducLog B \text{ et } B \in \mathscr{C}}$.
%\end{defn}

\begin{defn}\cite{C71a}
$A = \tupl{\Sigma}{\Gamma}{B}{\Pi}{Z_0}{Q}{q_0}{q_a}{q_r}{\delta}$ est un \gls{AuxDPDA} où la seule différence avec une \gls{mT} est:
\begin{itemize}
\item $\Pi$ est l'alphabet de pile, un ensemble fini
\item $Z_0 \in \Pi \setminus \Sigma$ est le symbole initial de pile
\item $\delta : \paren{Q \setminus \setTwo{q_a}{q_r}} \times \Sigma \times \Gamma \times \Pi \to Q \times \Gamma \times \paren{\Pi \cup \setOne{\varepsilon}} \times \setThree{\mathrm{G}}{\mathrm{S}}{\mathrm{D}}^2$ est la fonction de transition
\end{itemize}
$\fofOne{L}{A}$ est le langage de $A$, l'ensemble des mots sur lesquels $A$ s'arrête dans l'état d'acceptation.
\end{defn}

\begin{defn}
$N = \tupl{\Sigma}{\Gamma}{B}{\Pi}{Z_0}{Q}{q_0}{q_a}{q_r}{\delta}$ est un \gls{AuxNPDA} où la seule différence avec un \gls{AuxDPDA} est:
\begin{itemize}
\item $\delta : \paren{Q \setminus \setTwo{q_a}{q_r}} \times \Sigma \times \Gamma \times \Pi \to \power{Q \times \Gamma \times \paren{\Pi \cup \setOne{\varepsilon}} \times \setThree{\mathrm{G}}{\mathrm{S}}{\mathrm{D}}^2}$ est la relation de transition
\end{itemize}
$\fofOne{L}{N}$ est le langage de $N$, l'ensemble des mots sur lesquels il existe un choix de transitions tels que $N$ s'arrête dans l'état d'acceptation.
\end{defn}

\begin{note}
Sauf indication contraire, on suppose dans le texte qu'un \gls{AuxPDA} est déterministe.
\end{note}

\begin{defn}
Soit $f_1$ et $f_2$ des fonctions, alors \resp{$\DAuxPDA{f_1}{f_2}$}{$\NAuxPDA{f_1}{f_2}$} est l'ensemble des langages décidés par un \resp{\gls{AuxDPDA} $M$}{\gls{AuxNPDA} $N$} telle que $\exists \alpha_1, \alpha_2 \in \N, \forall x \in \Sigma^*$ \resp{$M$ sur $x$}{$N$ sur $x$} fonctionne en temps au plus $\alpha_1 \fofOne{f_1}{\len{x}}$ et utilise au plus $\alpha_2 \fofOne{f_2}{\len{x}}$ espace sur son ruban de travail \respOne{peu importe le choix des transitions} (sans compter l'espace de la pile).

Soit $F_1$ et $F_2$ des ensembles de fonctions, alors \resp{$\DAuxPDA{F_1}{F_2}$ est $\displaystyle\bigcup_{\lstTwo{f_1 \in F_1}{f_2 \in F_2}} \DAuxPDA{f_1}{f_2}$}{$\NAuxPDA{F_1}{F_2}$ est $\displaystyle\bigcup_{\lstTwo{f_1 \in F_1}{f_2 \in F_2}} \NAuxPDA{f_1}{f_2}$}.
\end{defn}

\section{Circuits Booléens}

Encore une fois, on peut trouver les notions de bases qui suivent dans \cite{P14}.

\begin{defn}
Soit $\CircuitFamily{C}{n}$ une famille de circuits booléens, alors $\CircuitFamily{C}{n}$ est \defin{uniforme} s'il existe une \gls{mT} $M$ qui calcule $\fofOne{M}{1^n} = \codeOne{C_n}$ -- la description du circuit -- telle que $\exists \alpha \in \N, \forall x \in \Sigma^*$, $M$ sur $x$ utilise au plus $\alpha \fofOne{\log}{\len{x}}$ espace sur chaque ruban de travail.
\end{defn}

\begin{defn}
Soit $C_n$ un circuit booléen et $s$ un sommet dans $C_n$, alors la \defin{hauteur} de $s$ est la longueur du plus long chemin de $s$ à une entrée ou une constante
\end{defn}

\begin{defn}
Soit $C_n$ un circuit booléen, alors la \defin{taille} de $C_n$, $\fofOne{T}{C_n}$, est le nombre de sommets dans le circuit et sa \defin{profondeur}, $\fofOne{P}{C_n}$, est la hauteur de la porte résultat du circuit.
\end{defn}

\begin{defn}
Soit $\alpha \in \N$, alors l'ensemble des langages décidés par une famille de circuits booléens $\CircuitFamily{C}{n}$ uniforme telle que $\exists f_1 \in n^{\bigO{1}}, f_2 \in \bigO{\fofOne{\log^{\alpha}}{n}}$ avec $\forall n \in \N$, $\fofOne{T}{C_n} \leq \fofOne{f_1}{n}$ et $\fofOne{P}{C_n} \leq \fofOne{f_2}{n}$ est:
\begin{itemize}
\item $\NC{\alpha}$ si les portes $\wedge$ et $\vee$ sont d'arités constantes (la classe de Nick ou \english{Nick's class})
\item $\SAC{\alpha}$ si les portes $\wedge$ sont d'arités constantes et $\vee$ d'arités illimitées (circuit alternant à arité semi-illimitée ou \english{semi-unbounded fan-in alternating circuit})
\item $\AC{\alpha}$ si les portes $\wedge$ et $\vee$ sont d'arités illimitées (circuit alternant ou \english{alternating circuit})
\end{itemize}
\end{defn}

%