\chapter{Circuits Multiplex} \begin{defn}\cite{FLR96}, \cite{MRV99} Soit $\CircuitFamily{C}{n}$ une famille de circuits et $k, l \in \bigO{\fofOne{\log}{n}}$ des fonctions, alors, dans un circuit $C_n$, une \defin{porte multiplex} (voir Figure \ref{multiplex-select-gate}) a comme arguments un paquet de $\fofOne{k}{n}$ bits guides et $2^{\fofOne{k}{n}}$ paquets de $\fofOne{l}{n}$ bits de données; sa seule sortie est un paquet de $\fofOne{l}{n}$ bits. Le calcul de la porte décode le nombre $j$ (où $0 \leq j \leq 2^{\fofOne{k}{n}} - 1$) représenté en binaire dans le paquet de bits guides, puis passe le $j$-ème paquet de bits de données en sortie. \end{defn} \begin{figure}[H] \centering \def\svgwidth{.5\textwidth} \input{./figures/mux_gate.pdf_tex} \caption{Une porte multiplex} \label{multiplex-select-gate} \end{figure} \begin{defn}\cite{MRV99} \defin{Un circuit multiplex} $C_n$ est un circuit booléen dont les sommets sont des entrées ou des portes multiplex. Une \defin{entrée} n'a pas d'argument, seulement une sortie de taille $1$. L'unique \defin{porte résultat} est spéciale car ses paquets de bits de données sont de taille $l = 1$ et sa sortie n'est utilisée comme argument d'aucune porte. Le calcul de $C_n$ sur $x = x_1x_2\dots x_n \in \alphabin{n}$ s'effectue en calculant la sortie de chaque porte, considérant que les entrées du circuit $\lstFour{\mathbf{x}_1}{\mathbf{x}_2}{\dots}{\mathbf{x}_n}$ ont respectivement une valeur $\lstFour{x_1}{x_2}{\dots}{x_n}$. Ainsi, $C_n$ accepte $x$ \ssi{} la sortie de la porte résultat est $1$. \end{defn} Dans un circuit multiplex on ne peut combiner plusieurs paquets de bits en un, ni séparer un paquet de bits en plusieurs; donc le paquet de bits en sortie d'un sommet doit servir, dans son entièreté, comme seul argument (guide ou donnée) d'une autre porte. La seule exception est qu'on peut ajouter $\bigO{\fofOne{\log}{n}}$ bits constants au début (i.e. bits moins significatifs) de tout paquet de bits du circuit $C_n$ d'une famille $\CircuitFamily{C}{n}$. \begin{defn} Un \defin{circuit multiplex fort} $C_n$ est un circuit multiplex où l'on permet deux nouveaux types de porte: \begin{itemize} \item Une porte \defin{juxtaposition} avec arguments $m \in \bigO{1}$ paquets de bits $\lstFour{b_1}{b_2}{\dots}{b_m}$ respectivement de tailles $\lstFour{t_1}{t_2}{\dots}{t_m} \in \bigO{\fofOne{\log}{n}}$ et les juxtapose en un seul paquet de bits $b_1 b_2 \dots b_m$ de taille $\bigO{\fofOne{\log}{n}}$ en sortie. \item Une porte \defin{extraction} avec arguments un paquet de bits $b$ de taille $t \in \bigO{\fofOne{\log}{n}}$ et deux paquets de bits constants $\lstTwo{b_1}{b_2}$ respectivement de tailles $\lstTwo{t_1}{t_2} \in \bigO{\fofOne{\log}{n}}$, avec $t_1 \leq t_2 \leq t$. La sortie est un paquet de bits de taille $t_2 - t_1 + 1$, constitué des bits indicés $t_1$ à $t_2$ du paquet de bits $b$. \end{itemize} \end{defn} \section{Classes de Complexité Multiplex} On utilise la même notion d'uniformité que pour une famille de circuits booléens. Dans le cas d'une famille de circuits multiplex $\CircuitFamily{C}{n}$, la description du circuit $\codeOne{C_n}$ est une liste de la description de chaque sommet dans $C_n$ avec celle de la porte résultat en premier. Chaque description d'un sommet est dotée d'un identifiant numérique unique qui est un mot binaire. Chaque entrée $\mathbf{x}_i$ est décrite ainsi: \[ \mathbf{x}\paren{s\#i} \] où $s$ est l'identifiant numérique du sommet et $i$ est écrit en binaire. Et chaque porte est décrite comme suit: \[ \mathbf{m}\paren{s\#g\#h\#d_0\#c_0\#d_1\#c_1\#\dots\#d_{2^k-1}\#c_{2^k-1}} \] où $g$ est l'identifiant numérique du sommet dont la sortie est utilisée comme paquet de bits guides, $h$ les bits constants du paquet de bits guides, $d_j$ l'identifiant numérique du sommet dont la sortie est utilisée comme le $j$-ème paquet de bits de données et $c_j$ les bits constants du $j$-ème paquet de bits de données. On utilise la même notion d'uniformité pour une famille de circuits multiplex forts. La seule différence est la description qui doit inclure les deux nouveaux types de porte; la porte juxtaposition: \[ \mathbf{j}\paren{s\#b_1\#c_1\#b_2\#c_2\#\dots\#b_m\#c_m} \] où $b_j$ est l'identifiant numérique du sommet dont la sortie est utilisée comme le $j$-ème paquet de bits d'entrées et $c_j$ les bits constants du $j$-ème paquet de bits d'entrées, puis la porte extraction: \[ \mathbf{e}\paren{s\#b\#c\#b_1\#b_2} \] où $b$ est l'identifiant numérique du sommet dont la sortie est utilisée comme argument $b$, $c$ la partie constante de ce dernier, $b_1$ et $b_2$ les paquets de bits constants. Avec la porte résultat comme racine, un circuit multiplex \respOne{fort} n'est pas un arbre dans le cas général, car la sortie d'un sommet peut servir comme argument à plus d'une porte. Il est possible de démêler le circuit, c'est à dire, de dupliquer chaque sommet et son sous-circuit autant de fois que sa sortie est utilisée comme argument d'une autre porte. Voici un exemple de pseudo-algorithme qui, avec les sommets d'un circuit multiplex comme entrée, donne l'arbre dont la racine est la porte résultat, \begin{algorithmic}[1] \While{$\exists s : \fofOne{\textsc{NombreParent}}{s} > 1$} \Comment{Parcourt les sommets en ordre d'identifiants numériques} \State{$p \gets \fofOne{\textsc{Parent}}{s}$} \Comment{Un des parents de $s$} \State{$s' \gets \fofOne{\textsc{Duplique}}{s}$} \Comment{Duplique $s$ et son sous-circuit, avec de nouveaux identifiants numériques} \State{Argument $s$ de $p \gets s'$} \Comment{Dans $p$, remplacer l'identifiant numérique de $s$ par $s'$} \EndWhile \end{algorithmic} \begin{defn}\cite{MRV99} \defin{L'arbre de preuve} du circuit multiplex \respOne{fort} $C_n$ sur entrée $x \in \alphabin{n}$ est le résultat de démêler le circuit, puis de supprimer les sommets qui ne contribuent pas au calcul de $C_n$ sur $x$. Ainsi, on ne conserve que le sommet qui calcule le paquet de bits guides et celui qui calcule le paquet de bits de données qui est sélectionné par les bits guides, et ce, pour chaque porte conservée en commençant par la porte résultat. \defin{La taille de l'arbre de preuve} de $C_n$, $\fofOne{TAP}{C_n}$, est la taille maximale ($\forall x \in \alphabin{n}$) d'un arbre de preuve sur $x$. \end{defn} \begin{defn} La taille du circuit multiplex \respOne{fort} $C_n$, $\fofOne{T}{C_n}$, est définie identiquement aux circuits booléens, c'est le nombre de sommets dans le circuit. \end{defn} %\begin{defn} %La hauteur d'une porte $s$ dans un circuit multiplex \respOne{fort} $C_n$, $\fofOne{H}{s}$, est la taille du chemin le plus long de $s$ à un sommet sans enfant (soit un sommet entrée, ou un sommet porte avec des arguments entièrement constants) %\end{defn} \begin{defn}\cite{MRV99} Soit $f_1$ et $f_2$ des fonctions, alors \resp{$\MuxClass{f_1}{f_2}$}{$\MuxStrongClass{f_1}{f_2}$} est l'ensemble des langages décidés par une famille de circuits multiplex \respOne{forts} $\CircuitFamily{C}{n}$ uniforme telle que $\exists \alpha_1, \alpha_2 \in \N, \forall n \in \N$, $\fofOne{TAP}{C_n} \leq \alpha_1 \fofOne{f_1}{n}$ et $\fofOne{T}{C_n} \leq \alpha_2 \fofOne{f_2}{n}$. Soit $F_1$ et $F_2$ des ensembles de fonctions, alors \resp{$\MuxClass{F_1}{F_2}$ est $\displaystyle\bigcup_{\lstTwo{f_1 \in F_1}{f_2 \in F_2}} \MuxClass{f_1}{f_2}$}{$\MuxStrongClass{F_1}{F_2}$ est $\displaystyle\bigcup_{\lstTwo{f_1 \in F_1}{f_2 \in F_2}} \MuxStrongClass{f_1}{f_2}$}. \end{defn} \begin{prop}\label{lem-MuxStrongEquiv} Soit $f_1$ et $f_2$ des fonctions, alors $\MuxClass{f_1}{f_2} \supseteq \MuxStrongClass{f_1}{f_2}$. \end{prop} \begin{proof} Soit $Y \in \MuxStrongClass{f_1}{f_2}$, alors $\exists \CircuitFamily{C}{n}$ une famille de circuits multiplex forts uniforme telle que $\exists \alpha_1, \alpha_2 \in \N, \forall n \in \N$, $\fofOne{TAP}{C_n} \leq \alpha_1 \fofOne{f_1}{n}$ et $\fofOne{T}{C_n} \leq \alpha_2 \fofOne{f_2}{n}$. On veut montrer $\exists \CircuitFamily{C'}{n}$ une famille de circuits multiplex uniforme qui décide aussi $Y$, telle que $Y \in \MuxClass{f_1}{f_2}$. Il faut donc un algorithme qui calcule la description d'un circuit multiplex $C'_n$ équivalent à un circuit multiplex fort $C_n$ dont la description est donnée en entrée. L'algorithme remplace chaque porte de $C_n$ par une ou plusieurs portes multiplex équivalentes. On remplace une porte juxtaposition avec arguments $\lstFour{b_1}{b_2}{\dots}{b_m}$ de tailles $\lstFour{t_1}{t_2}{\dots}{t_m}$ par une série de $m - 1$ portes multiplex (voir Figure \ref{merge-gate}). Chaque porte multiplex sélectionne le paquet de bits de données qui contient les bits constants dont la valeur est égale à celle du paquet de bits guides. Ainsi, la porte juxtapose le paquet de bits guides au paquet de bits qui est dupliqué sur chaque argument de donnée. Pour ce qui est de l'identifiant numérique de la porte juxtaposition, celui-ci est copié pour la dernière porte multiplex et les précédentes obtiennent de nouveaux identifiants. Donc, si la sortie de la porte juxtaposition était utilisée dans $C_n$, elle le sera de la même façon dans $C'_n$. On remplace une porte extraction avec argument $b$ de taille $t$ et deux autres arguments de tailles $t_1$ et $t_2$ par une porte multiplex. Le paquet $b$ sert de paquet de bits guides et chaque paquet de bits de données est un paquet de $t_2 - t_1 + 1$ bits constants. Sur le $j$-ème paquet de bits de données, on a $j$ en binaire, mais seulement les bits d'indices de $t_1$ à $t_2$ (inclusivement). Pour ce qui est de l'identifiant numérique, il est simplement copié tel quel. Maintenant qu'on a que $\CircuitFamily{C'}{n}$ décide aussi $Y$, on veut que la famille soit uniforme. L'algorithme doit donc fonctionner en espace $\bigO{\fofOne{\log}{n}}$. On effectue le remplacement de la porte juxtaposition une porte multiplex à la fois. Pour écrire la description de la porte multiplex qui a $b_i$ ($2 \leq i \leq m$) comme paquet de bits guides, il suffit d'écrire $b_i$ et $b_{i - 1}$ aux bons endroits et de compter sur $t_i \in \bigO{\fofOne{\log}{n}}$ bits. Au total, le remplacement utilise donc $\bigO{m \fofOne{\log}{n}} = \bigO{\fofOne{\log}{n}}$ espace. Pour effectuer le remplacement d'une porte extraction, il suffit d'écrire $b$ au bon endroit et de compter sur $t \in \bigO{\fofOne{\log}{n}}$ bits pour seulement copier les bits de $t_1$ à $t_2$ à chaque nombre, donc en espace $\bigO{\fofOne{\log}{n}}$. Soit une \gls{mT} qui, sur entrée $1^{n}$, calcule bit à bit la description de $C_n$ (qui s'effectue en espace $\bigO{\fofOne{\log}{n}}$, étant donné l'uniformité de $\CircuitFamily{C}{n}$). Pour chaque bit, on réutilise l'espace pour calculer $C'_n$ avec l'algorithme de remplacement décrit précédemment. Ainsi, $\CircuitFamily{C'}{n}$ est uniforme. Par la suite, on doit montrer des bornes sur $\fofOne{TAP}{C'_n}$ et $\fofOne{T}{C'_n}$ telles qu'on puisse affirmer $Y \in \MuxClass{f_1}{f_2}$. Soit $m_{max} \in \bigO{1}$ le maximum du nombre d'arguments d'une porte juxtaposition dans $\CircuitFamily{C}{n}$. Le remplacement d'une porte juxtaposition dans $C_n$ par des portes multiplex dans $C'_n$ augmente la taille d'arbre de preuve d'au plus $m_{max}- 1$. En effet, peu importe l'entrée $x$, l'arbre de preuve pour $C'_n$ ne conserve qu'une seule copie de chaque porte multiplex parmi celles qui remplacent une porte juxtaposition. Pour ce qui est de la taille du circuit, celle-ci augmente aussi d'au plus $m_{max}- 1$. Le remplacement de la porte extraction dans $C_n$ par une porte multiplex dans $C'_n$ ne change pas la taille du circuit car on remplace un sommet par un autre. Il en est de même pour la taille d'arbre de preuve car l'unique argument non-constant de la porte extraction est utilisé une seule fois comme argument de la porte multiplex. Ainsi, la duplication pour calculer la $\fofOne{TAP}{C'_n}$ produit le même résultat que pour $\fofOne{TAP}{C_n}$. Avec $\alpha'_1 = \alpha_1 \paren{m_{max}- 1}$ et $\alpha'_2 = \alpha_2 \paren{m_{max}- 1}$, on a donc que $\CircuitFamily{C'}{n}$ est une famille de circuits multiplex uniforme qui décide $Y$ telle que $\forall n \in \N$, $\fofOne{TAP}{C'_n} \leq \alpha'_1 \fofOne{f_1}{n}$ et $\fofOne{T}{C'_n} \leq \alpha'_2 \fofOne{f_2}{n}$. \end{proof} \begin{cor}\label{prop-MuxStrongEquivSet} Soit $F_1$ et $F_2$ des ensembles de fonctions, alors $\MuxClass{F_1}{F_2} = \MuxStrongClass{F_1}{F_2}$. \end{cor} \begin{proof} $\subseteq$ : $Y \in \MuxClass{F_1}{F_2}$ implique que $\exists f_1 \in F_1, f_2 \in F_2$ telles que $Y \in \MuxClass{f_1}{f_2}$. Parce qu'une famille de circuits multiplex uniforme est aussi une famille de circuits multiplex forts uniforme avec la même taille d'arbre de preuve et taille, on a que $Y \in \MuxStrongClass{f_1}{f_2} \subseteq \MuxStrongClass{F_1}{F_2}$. $\supseteq$ : $Y \in \MuxStrongClass{F_1}{F_2}$ implique que $\exists f_1 \in F_1, f_2 \in F_2$ telles que $Y \in \MuxStrongClass{f_1}{f_2}$. Par le lemme \ref{lem-MuxStrongEquiv}, on a que $Y \in \MuxClass{f_1}{f_2} \subseteq \MuxClass{F_1}{F_2}$. \end{proof} \clearpage \vspace*{\fill} \begin{minipage}{\textwidth} \centering \def\svgwidth{.5\textwidth} \input{./figures/mux_merge.pdf_tex} \captionof{figure}{Simulation d'une porte juxtaposition avec $m - 1 \in \bigO{1}$ portes multiplex} \label{merge-gate} \end{minipage} \vspace*{\fill} \clearpage \section{Les \textsf{\gls{AuxDPDA}} Capturent \textsf{LOGDCFL}} \newcommand{\DerniereConfig}[1]{\fofOne{\textsc{DernièreConfig}}{#1}} \begin{prop}\cite{MRV99}\label{lem-DAuxPDAMux} $\DAuxPDA{n^{\bigO{1}}}{\bigO{\fofOne{\log}{n}}} \subseteq \MuxClass{n^{\bigO{1}}}{n^{\bigO{1}}}$. \end{prop} \begin{proof} Soit $f_1 \in n^{\bigO{1}}$, $f_2 \in \bigO{\fofOne{\log}{n}}$, $\alpha_1, \alpha_2 \in \N$ et $A$ un \gls{AuxPDA} qui -- sur $x \in \Sigma^*$ quelconque -- 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. Sans perte de généralité, on assume que $A$ doit empiler ou dépiler un symbole de sa pile à chaque transition. Cette restriction fait partie du folklore \cite{HU79}. Simplement, si $\exists A'$ un \gls{AuxPDA} qui ne respecte pas cette hypothèse, il suffit de construire $A$ qui simule $A'$ sauf lorsque ne fait rien avec sa pile. Dans ce dernier cas $A$ empile un symbole inutile qui dépilé à la prochaine transition. Ainsi, le temps de calcul de $A$ est au pire le double de celui de $A'$. Encore sans perte de généralité, on assume que $A$ doit terminer avec une pile vide. En effet, si $\exists A'$ un \gls{AuxPDA} qui ne respecte pas cette hypothèse, il suffit de construire $A$ qui simule $A'$ jusqu'à ce qu'il entre dans un état \resp{d'acceptation}{de refus}. Dans ce cas $A$ dépile sa pile en entier et puis s'arrête et \resp{accepte}{refuse}. Similairement, le temps de calcul de $A$ est au pire le double de celui de $A'$. Afin d'expliciter la famille de circuit uniforme $\CircuitFamily{C}{n}$ qui décide $\fofOne{L}{A}$ avec taille d'arbre de preuve et taille polynomiales, on construit une \gls{mT} $M$ tel que $\fofOne{M}{1^n} = \codeOne{C_n}$ Le circuit $C_n$ simule le calcul de $A$ sur $x \in \Sigma^n$ en travaillant sur $K$ l'ensemble des configurations de surface (\english{surface configurations} dans \cite{MRV99} et \cite{C71a}), simplement configurations par la suite. Ainsi, on note $k = \tupl{t}{i}{x_i}{r}{j}{q}{Z}$ une configuration de $A$ où $t$ est le temps de calcul, \resp{$i$}{$j$} la position de la tête de lecture sur le ruban \resp{d'entrée}{de travail}, $x_i$ le symbole lu sur le ruban d'entrée, $r$ le contenu du ruban de travail, $q$ l'état et $Z$ le symbole sur le dessus de la pile. Par la suite, un indice quelconque (e.g. $a$) sur un élément d'une configuration (e.g. $t_a$ ou $x_{i_a}$) impliquera que cet élément appartient à la configuration avec le même indice (e.g. $k_a$). On note aussi que $\forall k \in K$, $\codeOne{k}$ est l'entier $\in \setFour{0}{1}{\dots}{\cardnSym{K} - 1}$. Pour chaque $k_1 \in K$, $C_n$ contient un circuit partiel qui calcule la dernière configuration accessible à partir de $k_1$ sans jamais dépiler plus bas que la hauteur de pile en $k_1$. Voici un algortihme qui illustre ce calcul nommé $\DerniereConfig{k_1}$: \newcommand{\CalculerEmpile}[2]{\fofTwo{\textsc{CalculerEmpile}}{#1}{#2}} \newcommand{\CalculerDepile}[3]{\fofThree{\textsc{CalculerDépile}}{#1}{#2}{#3}} \begin{algorithmic}[1] \Procedure{DernièreConfig}{$\,k_1\,$} \If{$\fofOne{\delta}{k_1}$ empile un symbole} \State $k_2 \gets \CalculerEmpile{x}{k_1}$ \Comment{$k_2$ est la configuration qui suit $k_1$ lorsque le mot en entrée est $x$} \State $k_3 \gets \DerniereConfig{k_2}$ \State $k_4 \gets \CalculerDepile{x}{k_3}{Z_1}$ \Comment{$k_4$ est la configuration qui suit $k_3$ lorsque le mot en entrée est $x$ et le symbole en dessous de $Z_3$ est $Z_1$} \State $k_5 \gets \DerniereConfig{k_4}$ \State \Return $k_5$ \Else \State \Return $k_1$ \label{algo-AuxMux-return} \EndIf \EndProcedure \end{algorithmic} Avant de montrer l'exactitude de l'algorithme, on note que $\forall k_1 \in K$ tel que $\fofOne{\delta}{k_1}$ empile un symbole, on a $t_1 < t_2 \leq t_3 < t_4 \leq t_5$ parce qu'il y a une transition qui empile entre $k_1$ et $k_2$ et une autre qui dépile entre $k_3$ et $k_4$. On a \resp{$t_2 = t_3$}{$t_4 = t_5$} seulement lorsque \resp{$\fofOne{\delta}{k_2}$}{$\fofOne{\delta}{k_4}$} est une transition qui dépile. \sloppy On pose $\Pred{h}$ qui est vérifié lorsque $\forall k_1 \in K$ tel que la pile va atteindre une hauteur supplémentaire de $h$ symboles à partir de $k_1$ avant de dépiler plus bas que la hauteur de pile en $k_1$, $\DerniereConfig{k_1}$ est exact. Pour $h = 0$, on a $\DerniereConfig{k_1} = k_1$ ce qui vérifie $\Pred{0}$. Pour $\Pred{h + 1}$, on doit avoir que $\fofOne{\delta}{k_1}$ empile un symbole, donc $k_3 = \DerniereConfig{k_2}$ est calculé correctement par hypothèse d'induction. Bien que $k_4$ revient à la même hauteur de pile que $k_1$, ceci s'est produit sans jamais dépiler en dessous de cette hauteur. Ainsi, parce que $t_1 < t_4$ et que $\range{\alpha_1 \fofOne{f_1}{n}}$ est fini, il suffit de répéter l'argument pour éventuellement arriver à cette dernière configuration accessible. Pour chaque $k_1 \in K$, $M$ écrit la description d'un circuit partiel qui calcule $\DerniereConfig{k_1}$. Si $\fofOne{\delta}{k_1}$ dépile, alors ce circuit partiel est une porte avec identifiant numérique $3\codeOne{k_1}$ et une sortie constante de $\codeOne{k_1}$. Dans le cas contraire, il contient trois portes (voir figure \ref{multiplex-aux-subcircuit}): \[ \mathbf{m}\paren{3\codeOne{k_1}+2\#3\cardnSym{K}+i_2\#\codeOne{k_1}\#d_0\#\#d_1\#\#\dots} \text{ où } d_{\codeTwo{x_{i_2}}{k_1}} = 3 \codeOne{k_2} \] \[ \mathbf{m}\paren{3\codeOne{k_1}+1\#3\codeOne{k_1}+2\#\#d_0\#c_0\#d_1\#c_ 1\#\dots} \text{ où } d_{\codeOne{k_3}} = 3\cardnSym{K}+i_4 \text{ et } c_{\codeOne{k_3}} = \codeTwo{k_3}{Z_1} \] \[ \mathbf{m}\paren{3\codeOne{k_1}\#3\codeOne{k_1}+1\#\#d_0\#\#d_1\#\#\dots} \text{ où } d_{\codeThree{x_{i_4}}{k_3}{Z_1}} = 3 \codeOne{k_4} \] Étant donné qu'une configuration inclut le symbole lu par la tête de lecture, la configuration initiale de $A$ -- dans notre contexte -- dépend du $x$ en entrée de $C_n$. Ainsi, $M$ doit ajouter une porte, $\mathbf{m}\paren{3\cardnSym{K}+n+1\#3\cardnSym{K}+1\#\#d_0\#\#d_1\#\#\dots}$ où $d_{\codeOne{x_1}} = 3 \codeOne{k_{\mathrm{init}}}$ et $k_{\mathrm{init}}$ est la configuration initiale de $A$ telle que $x_1$ est le symbole lu. Aussi, $M$ ajoute $\mathbf{m}\paren{3\cardnSym{K}+n+2\#3\cardnSym{K}+n+1\#\#d_0\#\#d_1\#\#\dots}$ où $d_{\codeOne{k}}$ est le bit $1$ si $k$ contient un état d'acceptation et le bit $0$ sinon, la porte résultat qui décide si $A$ refuse $x$ selon l'état contenu dans $\DerniereConfig{k_{\mathrm{init}}}$. Finalement, $M$ ajoute la description de chaque entrée $x_i$, $\mathbf{x}\paren{3\cardnSym{K}+i\#i}$. On montre à présent que $\CircuitFamily{C}{n}$ est uniforme. Pour ce faire, on doit calculer $\forall n \in \N, \fofOne{T}{C_n} = 3 \cardnSym{K} + n + 2$, ce qui requiert la taille de $K$: \[ \cardnSym{K} = \underbrace{\alpha_1 \fofOne{f_1}{n}}_{\text{temps}} \cdot \underbrace{n}_{\text{position entrée}} \cdot \underbrace{\cardnSym{\Sigma}}_{\text{symbole entrée}} \cdot \underbrace{\cardnSym{\Gamma}^{\alpha_2 \fofOne{f_2}{n}}}_{\text{contenu travail}} \cdot \underbrace{\alpha_2 \fofOne{f_2}{n}}_{\text{position travail}} \cdot \underbrace{\cardnSym{Q}}_{\text{état}} \cdot \underbrace{\cardnSym{\Pi}}_{\text{symbole pile}} \] % % TODO : Démêler cette preuve d'uniformité % Ainsi $\forall n \in \N, \fofOne{T}{C_n} \in \bigO{\fofOne{f_1}{n} \cdot 2^{\fofOne{f_2}{n}} \cdot n}$, ce qui veut dire $\exists \alpha_3 \in \N, f_3 \in n^{\bigO{1}}$ tels que $\forall n \in \N, \fofOne{T}{C_n} \leq \alpha_3 \fofOne{f_3}{n}$. Le calcul de $M$ consiste donc à réutiliser son espace logarithmique pour construire la description de chaque sommet de $C_n$. Cette tâche s'effectue bel et bien en espace logarithmique étant donné que pour écrire la description de chaque sommet, il suffit soit d'arithmétique sur les identifiants numériques des sommets soit du calcul d'une transition d'une configuration à la prochaine. Le dernier détail important pour l'uniformité est que la porte résultat -- celle avec identifiant $3\cardnSym{K}+n+2$ -- soit écrite en premier dans $\codeOne{C_n}$. % % % %on prouve l'uniformité du circuit ($M$ fonctionne en logspace) % Ici on a la preuve que T(Cn) est poly %$\forall n \in \N, \fofOne{T}{C_n} \leq 2 + 3\cardnSym{K} + n$ et $\cardnSym{K} = \alpha_1 \fofOne{f_1}{n} \cdot \cardnSym{\Gamma}^{\alpha_2 \fofOne{f_2}{n}} \cdot n \cdo\tuplTwo{1}{k}t \cardnSym{\Sigma} \cdot \cardnSym{Q} \cdot \cardnSym{\Pi}$. $\cardnSym{K} \in n^{\bigO{1}}$, donc $\exists \alpha_3 \in \N, f_3 \in n^{\bigO{1}}$ tels que $\forall n \in \N, \fofOne{T}{C_n} \leq \alpha_3 \fofOne{f_3}{n}$. % Ici on a la preuve que TAP(Cn) est poly %$\forall k_1 \in K$ tel que $\fofOne{\delta}{k_1}$ empile un symbole, on a $t_1 < t_2 \leq t_3 < t_4 \leq t_5$ parce qu'il y a une transition qui empile entre $k_1$ et $k_2$ et une autre qui dépile entre $k_3$ et $k_4$. On a \resp{$t_2 = t_3$}{$t_4 = t_5$} seulement lorsque \resp{$\fofOne{\delta}{k_2}$}{$\fofOne{\delta}{k_4}$} est une transition qui dépile. %Afin de montrer que $\forall n \in \N, x \in \Sigma^n$ l'arbre de preuve de $C_n$ sur $x$ contient au plus une porte $3 \codeOne{k}$ pour chaque $k \in K$, on construit une séquence par récurrence de configurations avec des $t$ distincts. %Par induction sur la hauteur d'une porte %Soit $\Pred{h}$ vérifié si $\forall n \in \N, x \in \Sigma^n, s \in C_n$ une porte de hauteur au plus $h$, l'arbre de preuve du sous-circuit de $s$ contient $\forall t \in \range{\alpha_1 \fofOne{f_1}{n}}$ au plus une porte avec identifiant $3 \codeOne{k}$. On montre à présent que $\forall n \in \N, x \in \Sigma^n$ l'arbre de preuve de $C_n$ sur $x$ est de taille polynomiale. On explique une notion essentielle à la définition du prédicat à venir. Soit $n \in \N, x \in \Sigma^n$ et $k_1 \in K$, alors parcourir en profondeur l'arbre de preuve du sous-circuit à partir de $k_1$ sur $x$ forme une séquence $S'$ des portes visitées. On note donc $\fofTwo{S}{x}{k_1}$ la séquence où l'on ne conserve que les paramètres $t$ des portes de forme $\exists k \in K, 3 \codeOne{k}$ à partir de la séquence $S'$. Soit $\Pred{h}$ vérifié si $\forall n \in \N, x \in \Sigma^n, k_1 \in K$ tel que les portes $3 \codeOne{k_1}$ et $3 \codeOne{k_1} + 2$ ont une hauteur d'au plus $h$ dans l'arbre de preuve de $C_n$ sur $x$, $\fofTwo{S}{x}{k_1}$ est strictement croissante. Pour $\Pred{0}$, la porte $3 \codeOne{k_1}$ est constante donc $\fofTwo{S}{x}{k_1}$ ne contient que $t_1$. Pour $\Pred{h + 1}$, le parcours en profondeur est en deux parties. La première partie commence avec $3 \codeOne{k_1} + 2$ qui a une hauteur d'au plus $h + 1$ donc, par hypothèse d'induction, $\fofTwo{S}{x}{k_2}$ est strictement croissante. La seconde partie commence avec $3 \codeOne{k_1}$ qui a aussi une hauteur d'au plus $h + 1$ donc, par hypothèse d'induction, $\fofTwo{S}{x}{k_4}$ est strictement croissante. On note que la séquence $\fofTwo{S}{x}{k_2}$ commence par $t_2$ et termine avec $t_3$, tandis que la séquence $\fofTwo{S}{x}{k_4}$ commence par $t_4$ et termine avec $t_5$. En combinant $\fofTwo{S}{x}{k_2}$ et $\fofTwo{S}{x}{k_4}$, on obtient une séquence strictement croissante qui vérifie $\Pred{h + 1}$ parce que, tel que discuté plus haut, $t_1 < t_2 \leq t_3 < t_4 \leq t_5$. On a donc que $\forall n \in \N, x \in \Sigma^n$ l'arbre de preuve de $C_n$ contient $\forall t \in \range{\alpha_1 \fofOne{f_1}{n}}$, au plus une porte $3 \codeOne{k}$ parce que $\fofTwo{S}{x}{k_{\mathrm{init}}}$ est strictement croissante. Avec deux sommets d'entrées pour chaque circuit partiel, la borne sur la taille de l'arbre de preuve est $\forall n \in \N, \fofOne{TAP}{C_n} \leq 5 \alpha_1 \fofOne{f_1}{n} + 2$. %Pour $h + 1$, on doit avoir $\exists k_1 \in K$ tel que ou bien $3 \codeOne{k_1}$ ou bien $3 \codeOne{k_1} + 2$ ait une hauteur d'au plus $h + 1$ dans l'arbre de preuve de $C_n$ sur $x$. Sans perte de généralité, on choisit $3 \codeOne{k_1}$ avec une hauteur supérieur à $h + 1$ %Chaque fois qu'on ajoute une porte dans la séquence %Chaque porte du sous-circuit % %$\forall k_1 \in K$ tel que $\fofOne{\delta}{k_1}$ empile un symbole, on a $t_1 < t_2 \leq t_3 < t_4 \leq t_5$ parce qu'il y a au moins une transition qui empile entre $k_1$ et $k_2$ et au moins une autre qui dépile entre $k_3$ et $k_4$ % %On suppose par contradiction $\exists x \in \Sigma^n, k_1 \in K$ tels que la porte $3 \codeOne{k_1}$ est présente plus d'une fois dans l'arbre de preuve de $C_n$ sur entrée $x$. Une première possibilité est que $\exists k'_1 \in K$ tel que les portes sélectionnées par $3 \codeOne{k'_1} + 2$ et $3 \codeOne{k'_1}$ soient tous deux $3 \codeOne{k_1}$, mais cela contredit $t'_2 < t'_4$. Une seconde possibilité est $\exists k'_1, k''_1 \in K$ différents tels que % %Ainsi, pour un $x \in \Sigma^*$ quelconque, une porte $3 \codeOne{k_1}$ n'est dans l'arbre de preuve qu'une seule fois % %Étant donné que $\forall k_1 \in K$ tel que $\fofOne{\delta}{k_1}$ empile un symbole, on a $t_1 < t_2 < t_4$, la porte $3 \codeOne{k_1}$ % % TODO : Démêler cette preuve TAP % %On montre à présent que $\forall n \in \N, x \in \Sigma^n$ l'arbre de preuve de $C_n$ sur $x$ est de taille polynomiale. Pour cela, on construit par récurrence, une séquence de configurations en ordre strictement croissant de leur paramètre $t$. %Dans un premier cas, on suppose que $\fofOne{\delta}{k_{\mathrm{init}}}$ dépile un symbole. Évidemment, la taille de l'arbre de preuve de $C_n$ sur $x$ sera constante. %Dans un second cas, on a que $\fofOne{\delta}{k_{\mathrm{init}}}$ empile un symbole. Ainsi, afin de respecter l'inégalitée $t_1 < t_2 \leq t_3 < t_4 \leq t_5$, ajouter la porte avec identifiant numérique $3 \codeOne{k_1} + 2$ à l'arbre de preuve proscrit les configurations $k \in K$ tels que $t \leq t_1$ d'apparaître dans l'arbre de preuve. %On a donc que l'arbre de preuve contient $\forall t \in \range{\alpha_1 \fofOne{f_1}{n}}$, au plus une porte $3 \codeOne{k}$. Parce que chaque circuit partiel utilise 2 copies des portes d'entrées. Une borne sur la taille de l'arbre de preuve est donc $\forall n \in \N, \fofOne{TAP}{C_n} \leq 5 \alpha_1 \fofOne{f_1}{n} + 2$. % % % Pour conclure, la famille de circuit multiplex uniforme $\CircuitFamily{C}{n}$ décide $\fofOne{L}{A}$ avec $\forall n \in \N, \fofOne{TAP}{C_n} \in n^{\bigO{1}}$ et $\fofOne{T}{C_n} \in n^{\bigO{1}}$. Donc $\fofOne{L}{A} \in \MuxClass{n^{\bigO{1}}}{n^{\bigO{1}}}$. \end{proof} \clearpage \vspace*{\fill} \begin{minipage}{\textwidth} \centering \def\svgwidth{.8\textwidth} \input{./figures/mux_aux.pdf_tex} \captionof{figure}{Circuit partiel avec chaque configuration $k_l = \tuplSeven{t_l}{i_l}{x_{i_l}}{r_l}{j_l}{q_l}{Z_l}$ représentant une étape de calcul, où selon la valeur $i$ du guide $g$ et $h$ l'argument de donnée $d_i$ et $c_i$ est sélectionné. (\resp{$g$ et $d_i$}{$h$ et $c_i$}) sont des \resp{identifiants de portes}{constantes})} \label{multiplex-aux-subcircuit} \end{minipage} \vspace*{\fill} \clearpage \begin{prop}\cite{MRV99}\label{lem-MuxLogDCFL} $\MuxClass{n^{\bigO{1}}}{n^{\bigO{1}}} \subseteq \LogDCFL$. \end{prop} \begin{proof} Soit $f_1, f_2 \in n^{\bigO{1}}$, $\alpha_1, \alpha_2 \in \N$ et $\CircuitFamily{C}{n}$ une famille de circuits multiplex uniforme qui décide $Y$ telle que $\forall n \in \N$, $\fofOne{TAP}{C_n} \leq \alpha_1 \fofOne{f_1}{n}$ et $\fofOne{T}{C_n} \leq \alpha_2 \fofOne{f_2}{n}$. Il faut donc exhiber un $Y' \in \DCFL$ et un transducteur $f$ qui fonctionne en espace logarithmique tel que $x \in Y \iff \fofOne{f}{x} \in Y'$. On montre donc que $Y'$ est reconnu par un \gls{DPDA} $A$. Description de $Y'$ : La forme générale d'un $\fofOne{f}{x}$ produit par le transducteur est une liste des descriptions de chacun des sommets de $C_{\len{x}}$ (similaire à la description naturelle d'un circuit multiplex) qui permettra à $A$ d'évaluer $C_{\len{x}}$ à la lecture de cette liste. Pour simplifier la construction de $A$, tous les sommets de $\fofOne{f}{x}$ sont des portes. $f$ convertit donc chaque entrée $\mathbf{x}_i$ en une porte où chaque argument est un paquet d'un bit constant de valeur $x_i$. Ainsi, pour évaluer le circuit décrit par $\fofOne{f}{x}$, il est inutile de lire $x$, car ce dernier est encodé dans $\fofOne{f}{x}$. Le calcul de $A$ sur $\fofOne{f}{x}$ commence par évaluer la porte résultat. Pour évaluer une porte $P$ avec identifiant numérique $s$ dans $C_{\len{x}}$, $A$ empile $s$, se déplace jusqu'à la description de $P$, puis évalue la porte qui fournit à $P$ son paquet de bits guides. Si, par contre, le paquet de bits guides de $P$ est entièrement constant, $A$ empile ces bits constants. Ensuite, $A$ se déplace jusqu'à la description de $P$, dans la section qui décrit le paquet de bits de données sélectionné par la valeur tout juste empilée, dépile cette valeur et $s$, puis empile l'identifiant de la porte qui fournit à $P$ le paquet de bits de données (ou bien les bits constants sélectionnés). $A$ continue ainsi de suite, jusqu'à ce que la pile ne contienne qu'un bit constant, la sortie de la porte résultat. Un premier problème avec cette stratégie est que la liste des descriptions de portes n'est pas nécessairement dans le bon ordre pour évaluer $\fofOne{f}{x}$ en la lisant d'une seule direction. Une solution est de répéter la liste plusieurs fois afin de permettre à $A$ de trouver la porte voulue même si l'automate la dépasse, elle sera dans la prochaine répétion de la liste. Le calcul de $A$ effectue un parcours en profondeur de l'arbre de preuve de $C_{\len{x}}$ sur $x$, en visitant chaque porte deux fois (une fois pour évaluer son paquet de bits guides et l'autre pour le paquet de bits de données). Répéter la liste $2 \alpha_1 \fofOne{f_1}{\len{x}}$ fois est donc suffisant. Un second problème avec le calcul de $A$ est que, pour se déplacer jusqu'à la description de la porte $P$ avec identifiant numérique $s$ recherchée, l'automate doit comparer $s$ sur sa pile avec chaque élément de la liste. Or, cette comparaison demande de dépiler les bits de $s$ pour y accéder. Si on ne trouve pas la description de $P$ immédiatement, le $s$ dépilé est perdu sans qu'on puisse se déplacer jusqu'à $P$. L'encodage de chaque identifiant numérique $s$ doit donc être suivi de son inverse $s^R$. Supposons que $A$ calcule sur entrée $\fofOne{f}{x} = \dots\paren{ubv\#v^Rbu^R}\dots$ et le dessus de la pile est $ub'\dots$ (ici, $b'$ est sous $u$ et le premier symbole de $u$ est au dessus de la pile), avec $u,v$ deux mots non-vides, $b$ un bit et $b'$ son complément. En lisant $u$, $A$ le dépile, puis l'automate détecte que $b$ diffère de $b'$ et continue en empilant $v$ (sa pile est donc maintenant $v^Rb'\dots$). Par la suite, l'automate continue à lire l'entrée (en dépilant $v^R$) jusqu'à détecter à nouveau une différence puis empile $u^R$ pour se retrouver à nouveau avec $ub'\dots$ au dessus de sa pile. Avec ces problèmes résolus, il est maintenant possible de formaliser le langage $Y'$. On pose donc $\fofOne{f}{x} := w^{2 \alpha_1 \fofOne{f_1}{\len{x}}}$ où $w$ est la concaténation $w_1w_2\dots w_{\fofOne{TAP}{C_{\len{x}}}}$ des descriptions de chaque sommet du circuit en tant que porte. Comme pour la description naturelle d'un circuit multiplex, les identifiants numériques et les bits constants sont tous écrits en binaire. Pour une porte avec identifiant numérique $s$ avec un paquet de bits guides de taille $k$, sa description est comme suit: \[ w_s := \paren{s\#s^R\#h^R\#g^R}w_{s,0}w_{s,1}\dots w_{s,2^k-1} \] où $g$ est l'identifiant numérique de la porte dont la sortie est utilisée comme paquet de bits guides et $h$ est la partie de bits constants du paquet de bits guides. Il est possible que $g$ ou $h$ soit vide, mais pas les deux. Aussi, $w_{s,j}$ est la description du $j$-ème paquet de bits de données d'une porte multiplex avec identifiant numérique $s$, comme suit: \[ w_{s,j} := \paren{j\$s\#s^R\$j^R\#c_j^R\#d_j^R} \] Dans cette description $j$ est écrit en binaire, $d_j$ est l'identifiant numérique de la porte dont la sortie est utilisée comme $j$-ème paquet de bits de données et $c_j$ est la partie de bits constants. Encore une fois, au plus un de $d_j$ et $c_j$ peut être vide. \newcommand{\LireRuban}{\fofZero{\textsc{LireRuban}}} \newcommand{\AvancerTete}{\fofZero{\textsc{AvancerTête}}} \newcommand{\VoirPile}{\fofZero{\textsc{VoirPile}}} \newcommand{\Depiler}{\fofZero{\textsc{Dépiler}}} \newcommand{\Empiler}[1]{\fofOne{\textsc{Empiler}}{#1}} \newcommand{\TesterConditionFin}{\fofZero{\textsc{TesterConditionFin}}} \newcommand{\TrouverIdentifiant}{\fofZero{\textsc{TrouverIdentifiant}}} \newcommand{\AvancerTeteJusqua}[1]{\fofOne{\textsc{AvancerTêteJusqua}}{#1}} \newcommand{\EmpilerJusqua}[1]{\fofOne{\textsc{EmpilerJusqua}}{#1}} Description de $A$ : Voici l'algorithme qui décrit le comportement de $A$ sur $\fofOne{f}{x}$, \begin{algorithmic}[1] \Loop \label{algo-MuxLogDCFL-loop} \If{$\VoirPile = \#$} \label{algo-MuxLogDCFL-ifvalue} \Comment{la pile ressemble à $\#j\$s\#\dots$} \State $\Depiler$ \State $\TesterConditionFin$ \label{algo-MuxLogDCFL-end} \Comment{la condition de fin du calcul se trouve dans cette procédure} \State $\TrouverIdentifiant$ \Comment{ceci trouve le $w_{s,j}$ qui correspond au $j\$s$ sur la pile} \While{$\VoirPile \neq \#$} \Comment{on dépile $j\$s$ pour empiler la sortie de la porte $s$} \State $\Depiler$ \EndWhile \State $\Depiler$ \State $\EmpilerJusqua{\#}$ \Comment{ceci empile $c_j$ du $w_{s,j}$ trouvé} \State $\Empiler{\#}$ \State $\EmpilerJusqua{)}$ \Comment{ceci empile $d_j$ du $w_{s,j}$ trouvé} \Else \label{algo-MuxLogDCFL-ifgate} \Comment{la pile ressemble à $s\#\dots$} \State $\TrouverIdentifiant$ \Comment{ceci trouve le $w_s$ qui correspond au $s$ sur la pile} \State $\Empiler{\$}$ \State $\EmpilerJusqua{\#}$ \Comment{ceci empile $h$ du $w_s$ trouvé} \State $\Empiler{\#}$ \State $\EmpilerJusqua{)}$ \Comment{ceci empile $g$ du $w_s$ trouvé} \EndIf \EndLoop \end{algorithmic} $\LireRuban$ retourne le symbole lu sur le ruban, $\AvancerTete$ déplace la tête de lecture d'une case à droite sur le ruban, $\VoirPile$ retourne le symbole au dessus de la pile, $\Depiler$ dépile le symbole au dessus de la pile et le retourne, $\Empiler{Z}$ empile le symbole $Z$ sur la pile. Les autres procédures utilisées sont décrites ici: \begin{algorithmic}[1] \Procedure{AvancerTêteJusqua}{$\,a\,$} \While{$\LireRuban \neq a$} \State $\AvancerTete$ \EndWhile \State $\AvancerTete$ \EndProcedure \end{algorithmic} \begin{algorithmic}[1] \Procedure{EmpilerJusqua}{$\,\tuplTwo{1}{k}a\,$} \While{$\LireRuban \neq a$} \State $\Empiler{\LireRuban}$ \State $\AvancerTete$ \EndWhile \State $\AvancerTete$ \EndProcedure \end{algorithmic} La procédure $\textsc{TrouverIdentifiant}$ fonctionne selon le principe expliqué en solution au second problème de la stratégie de calcul initiale de $A$. \begin{algorithmic}[1] \Procedure{TrouverIdentifiant}{} \Comment{trouve $w_s$ ou $w_{s,j}$ qui correspond au $s$ ou $j\$s$ sur la pile} \State $\mathrm{trouv\acute{e}} \gets \mathrm{non}$ \While{$\mathrm{trouv\acute{e}} = \mathrm{non}$} \State $\AvancerTeteJusqua{(}$ \State $\mathrm{diff\acute{e}rence} \gets \mathrm{inconnu}$ \While{$\mathrm{diff\acute{e}rence} = \mathrm{inconnu}$} \If{$\LireRuban = \VoirPile = \#$} \Comment{on atteint la fin de l'identifiant, sans différence} \State $\mathrm{diff\acute{e}rence} \gets \mathrm{non}$ \State $\mathrm{trouv\acute{e}} \gets \mathrm{oui}$ \ElsIf{$\LireRuban \neq \VoirPile$} \State $\mathrm{diff\acute{e}rence} \gets \mathrm{oui}$ \Else \State $\AvancerTete$ \State $\Depiler$ \EndIf \EndWhile \State $\EmpilerJusqua{\#}$ \Comment{on empile ce qui suit la différence trouvée (sinon, rien)} \While{$\LireRuban = \VoirPile$} \State $\AvancerTete$ \State $\Depiler$ \EndWhile \State $\EmpilerJusqua{\#}$ \Comment{ceci rétablit la pile comme elle était au début de la procédure} \EndWhile \EndProcedure \end{algorithmic} La procédure $\textsc{TesterConditionFin}$ arrête le calcul de $A$ si la condition de fin est atteinte. Pour arrêter, $A$ doit avoir exactement $bZ_0$ sur sa pile, où $Z_0$ est le symbole initial de pile et $b$ un bit qui indique l'acceptation ou non. La procédure dépile donc le symbole du dessus de pile pour vérifier que celui en dessous est $Z_0$, sinon elle rétablit la pile. \begin{algorithmic}[1] \Procedure{TesterConditionFin}{} \State $\mathrm{Z} \gets \Depiler$ \Comment{À la fin de la simulation, ceci contient la sortie du circuit} \If{$\VoirPile = Z_0$ et $\mathrm{Z} = 1$} \State $A$ s'arrête et accepte \ElsIf{$\VoirPile = Z_0$ et $\mathrm{Z} = 0$} \State $A$ s'arrête et refuse \Else \State $\Empiler{\mathrm{Z}}$ \Comment{Il faut empiler à nouveau, car ce n'est pas la fin de la simulation} \EndIf \EndProcedure \end{algorithmic} Il faut maintenant prouver que l'algorithme qui décrit le comportement de $A$ sur $\fofOne{f}{x}$ est correct. On montrera par induction que $\Pred{n}$ est vérifié $\forall n \geq 0$, où $\Pred{n}$ est vérifié si $\forall s$ identifiant numérique d'une porte de hauteur $n$, $A$ commence avec $s\#u$ sur le dessus de sa pile ($u$ est le mot quelconque qu'est le reste de la pile), à la ligne \ref{algo-MuxLogDCFL-loop} et (sans changer $u$) obtient $\#cu$ sur le dessus de sa pile, à la même ligne \ref{algo-MuxLogDCFL-loop}, où $c \in \alphabin{*}$ est la sortie de $s$. Pour $\Pred{0}$, $A$ a $s\#u$ sur le dessus de sa pile, à la ligne \ref{algo-MuxLogDCFL-loop}. $A$ entre dans la condition à la ligne \ref{algo-MuxLogDCFL-ifgate} et parcourt son ruban jusqu'au prochain $w_s$, puis empile le $h$ correspondant, ce qui donne un dessus de pile $\#h\$s\#u$ (la hauteur de $s$ est 0, ce qui implique que le $g$ correspondant est vide, ce qui implique que $h$ est non-vide). Ensuite, $A$ revient à la ligne \ref{algo-MuxLogDCFL-loop} puis entre dans la condition à la ligne \ref{algo-MuxLogDCFL-ifvalue}. $A$ ne termine pas en ligne \ref{algo-MuxLogDCFL-end}, mais parcourt son ruban jusqu'au prochain $w_{s,h}$, puis dépile pour avoir $u$ sur sa pile et puis empile $c_h$, la sortie de $s$, ce qui donne $\#c_hu$ (encore une fois, hauteur de $s$ est 0, ce qui implique que $d_h$ est vide, ce qui implique que $c_h$ est non-vide). Pour $\clause{\forall m \leq n, \Pred{m}} \implies \Pred{n+1}$, $A$ a $s\#u$ sur le dessus de sa pile, à la ligne \ref{algo-MuxLogDCFL-loop}, avec $s$ l'identifiant d'une porte de hauteur $n + 1$. $A$ entre dans la condition à la ligne \ref{algo-MuxLogDCFL-ifgate} et parcourt son ruban jusqu'au prochain $w_s$, puis empile les $h$ et/ou $g$ correspondant(s), ce qui donne trois dessus de piles possibles (mais tous reviennent à la ligne \ref{algo-MuxLogDCFL-loop}): \begin{enumerate} \item $g\#h\$s\#u$ (si $h$ et $g$ sont non-vides) \item $g\#\$s\#u$ (si $h$ est vide) \item $\#h\$s\#u$ (si $g$ est vide) \end{enumerate} Pour les cas un et deux, on sait que la hauteur de la porte avec identifiant $g$ est bornée par $n$, on utilise donc l'hypothèse d'induction et ces cas deviennent respectivement $\#ch\$s\#u$ et $\#c\$s\#u$ avec $c$ la sortie de la porte $g$. Pour la suite, on considère que $h'$ est une constante qui représente $ch$, $c$ ou $h$ selon l'un des trois cas. Donc, $A$ a $\#h'\$s\#u$ comme dessus de pile et est à la ligne \ref{algo-MuxLogDCFL-loop}. Ensuite, $A$ entre dans la condition à la ligne \ref{algo-MuxLogDCFL-ifvalue} et parcourt son ruban jusqu'au prochain $w_{s,h'}$, puis remplace le dessus de sa pile par $c_{h'}$ et/ou $d_{h'}$, ce qui donne trois dessus de piles possibles (mais tous reviennent à la ligne \ref{algo-MuxLogDCFL-loop}): \begin{enumerate} \item $d_{h'}\#c_{h'}u$ (si $c_{h'}$ et $d_{h'}$ sont non-vides) \item $d_{h'}\#u$ (si $c_{h'}$ est vide) \item $\#c_{h'}u$ (si $d_{h'}$ est vide) \end{enumerate} Pour les cas un et deux, on sait que la hauteur de la porte avec identifiant $d_{h'}$ est bornée par $n$, on utilise donc l'hypothèse d'induction et ces cas deviennent respectivement $\#c'c_{h'}u$ et $\#c'u$ avec $c'$ la sortie de la porte $d_{h'}$. Ainsi, $A$ obtient la sortie de $s$ (sous forme de $c'c_{h'}$, $c'$ ou $c_{h'}$) sur sa pile et en revenant à la même ligne \ref{algo-MuxLogDCFL-loop}. Avant d'exécuter l'algorithme principal, $A$ initialise son calcul en empilant l'identifiant numérique $s_0$ de la première porte dans $\fofOne{f}{x}$, qui est la porte résultat tel que promit par l'uniformité de $\CircuitFamily{C}{n}$. $A$ commence donc son calcul avec $s_0\#Z_0$ sur le dessus de sa pile à la ligne \ref{algo-MuxLogDCFL-loop} et, parce que $\Pred{\len{x}}$ est vérifié, va revenir sur cette même ligne avec sa pile $\#bZ_0$, où $b$ est la sortie $0$ ou $1$ de la porte résultat. Finalement, $A$ entre dans la condition à la ligne \ref{algo-MuxLogDCFL-ifvalue} et, avec $\TesterConditionFin$ va accepter ou refuser selon $b$. Description de $f$ : la réduction parcourt la description naturelle de $C_{\len{x}}$ puis écrit sur son ruban de sortie pour chaque sommet rencontré dans le même ordre. On répète ensuite cette procédure $2 \alpha_1 \fofOne{f_1}{\len{x}}$ fois. Pour un sommet d'entrée $\mathbf{x}_i$ avec identifiant numérique $s$, $f$ écrit: \[ w_s := \paren{s\#s^R\#x_i\#}\paren{0\$s\#s^R\$0\#0\#}\paren{1\$s\#s^R\$1\#1\#} \] Pour un sommet porte multiplex avec identifiant numérique $s$, $f$ écrit $w_s$ selon les $s$, $g$, $h$ dans la description naturelle (inversés au besoin). Pour écrire les $w_{s,j}$, $f$ compte $0 \leq j \leq 2^k-1$ puis utilise $c_j$ et $d_j$ inversés. $f$ produit donc correctement $\fofOne{f}{x}$ et ce, en espace logarithmique. En effet, la réduction peut accéder à un bit de la description naturelle de $C_{\len{x}}$ (grâce à l'uniformité de $\CircuitFamily{C}{n}$). Pour ce qui est du comptage nécessaire jusqu'à $\alpha_2 \fofOne{f_2}{\len{x}}$, $2 \alpha_1 \fofOne{f_1}{\len{x}}$ ou $2^k-1$, cela se fait sur $\bigO{\fofOne{\log}{\len{x}}}$ bits car $\fofOne{f_1}{\len{x}} \in \len{x}^{\bigO{1}}$ et $k \in \bigO{\fofOne{\log}{\len{x}}}$. \end{proof} \begin{cor}\cite{MRV99} $\LogDCFL = \DAuxPDA{n^{\bigO{1}}}{\bigO{\fofOne{\log}{n}}}$. \end{cor} \begin{proof} $\subseteq$ : La \gls{AuxPDA} réutilise son espace $\bigO{\fofOne{\log}{n}}$ pour calculer chaque bit du résultat de la réduction promise par $\LogDCFL$, puis utilise sa pile pour effectuer une transition de l'automate à pile propre au $\mathit{DCFL}$ selon le bit obtenu. Étant donné que la réduction promise par $\LogDCFL$ utilise un espace $\bigO{\fofOne{\log}{n}}$, le calcul de chaque bit nécessite un temps $n^{\bigO{1}}$ et il y a $n^{\bigO{1}}$ bits, le produit est donc un temps $n^{\bigO{1}}$. $\supseteq$ : Est une conséquence directe des lemmes \ref{lem-DAuxPDAMux} et \ref{lem-MuxLogDCFL}. \end{proof}