algo-best-alt.tex

% !TEX root = main.tex
%

%\florent{New Algorithm for best-search}
We shall compute the values of the functions $b_\bot$ and $b_\top$
by search of shortest paths in a $\Semiring$-labeled graph $\G_A$
associated to the \SWVPA $A$. 
This graph is defined by $\G_A = \< V_A, E_A, \eta_A >$, 
with set of vertices $V_A = (Q \times Q) \cup (Q \times P \times Q)$,
set of edges $E_A = V_A \times V_A$
(an edge $\< v_1, v_2>$, with $v_1, v_2 \in V_A$ is denoted by $v_1 \to v_2$),
and with an edge labelling  
$\eta_A : E_A \to \Semiring$ defined by, %as follows,
for $q_0, q_1, q_2, q_3 \in Q$, $p, p' \in P$:
%
\[
\begin{array}{rclcl}
%
\< q_0, q_1> & \to & \< q_0, q_2> & \mapsto &
\bigoplus_{\Deltai} \weiei(q_1, q_2) \oplus \bigoplus_{\Deltar} \weier(q_1, q_2)\\
%
\< q_0, q_1> & \to & v & \mapsto & \zero 
\quad \mathrm{if}\ v \in Q\setminus \{ q_0 \} \times Q\  \mathrm{or}\  v \in Q \times P \times Q\\
%
\< q_1, p, q_2> & \to & \<q_0, q_3> & \mapsto &
\bigoplus_{\Deltac} \bigl[ \weiec(q_0, p, q_1) \otimes \bigoplus^2_{\Deltar} \weir(q_2, p, q_3)\bigr]\\ 
%
%\< q_0, p, q_1> & \to & \< q_0, p, q_2> & : &
%\bigoplus_{\Deltai} \weii(q_1, p, q_2)\\
%
\< q_1, p', q_2> & \to & \< q_0, p, q_3> & \mapsto &
{\displaystyle\bigoplus_{q_0=q_1}}
{\displaystyle\bigoplus_{p=p'}}
{\bigoplus_{\Deltac}}
 \left[
 \begin{array}{l}
 \bigoplus^2_{\Deltai} \weii(q_2, p, q_3) \oplus\\
 % & & & &  \qquad\quad 
 \weic(q_0, p, p', q_1) \otimes_2 {\bigoplus^2_{\Deltar}} \weir(q_2, p', q_3) 
 \end{array}
 \right]
%
\end{array}
\]
%Removing from $\G_A$ every edge $e \in E_A$ such that $\eta(e) = \zero$ 
%is preserving the results below.
%
A \emph{path} of $\G_A$ is a sequence $\pi = v_0,\ldots, v_n \in V^*_A$,
where $v_0$ and $v_n$ are respectively called $\fst(\pi)$ and $\last(\pi)$.
The path $\pi$ is called \emph{safe} when $\fst(\pi)$ has the form $\< q, q>$ for some $q \in Q$, 
%
A path $\pi$ is assigned a weight value $\weight(\pi) \in \Semiring$ which is the product by $\otimes$ 
of the weights of the edges involved in the path.
More precisely, for all $q, q' \in Q$ and $p \in P$, we let 
$\weight(\< q, q' > ) = \one$ if $q = q'$, and $\zero$ otherwise, 
$\weight(\< q, p, q' > ) = \zero$ and 
for all $n \geq 1$, 
$\weight(v_0,\ldots, v_n) = \weight(v_0,\ldots, v_{n-1}) \otimes \eta_A(v_{n-1} \to v_{n})$.
%$\weight(\pi) = \bigotimes_{i=1}^{n} \eta(v_{i-1} \to v_i)$.
%
%The following results establish that $b_\bot(q, q')$ by be computed from a shortest path in $\G_A$.
For $v, v' \in V_A$,
let $\Pi_{v, v'}$ be the set of pathes $\pi$ such that 
$\fst(\pi) = v$ and $\last(\pi) = v'$, 
and let $\mathit{short}(v, v')$ be the weight of the shortest path from $v$ to $v'$, 
more precisely, 
\(\mathit{short}(v, v') = \displaystyle\bigoplus_{\pi\in \Pi_{v, v'}} \weight(\pi)\).

\begin{proposition}\label{algo-shortest}
%Let  and let $\pi$ be the shortest safe path with $\last(\pi) = \< q, q'>$, i.e. 
For all $q, q' \in Q$, 
$b_\bot(q, q') = \displaystyle\bigoplus_{q_0 \in Q} \mathit{short}\bigl(\< q_0, q_0>, \< q, q'>\bigr)$.
\end{proposition}
This proposition is a consequence of Lemmata~\ref{algo-correct} and~\ref{algo-complete} 
found in~Appendix \ref{app:shortpath}.

\medskip\noindent
Following~\eqref{eq:min} and Proposition~\ref{algo-shortest}, 
in order to compute the minimum of $t \mapsto A(t)$ \wrt $\leq_\oplus$, 
it is sufficient to compute one shortest paths in $\G_{A}$ of source
$\<q_0, q_0>$ and target $\<q, q'>$ for all $q_0, q, q' \in Q$.
This can be done~\cite{Mohri02semiring}  
with an overall worst case time complexity in $O\bigl(|Q|^2.|P|)^3\bigr)$. 
%Altogether, the complexity for computing the minimum of $A$ is in 
%worst case $O(...)$.
Moreover, a witness $t \in \Delta^*$ for this minimum can be associated to the appropriate
shortest path, with no additional cost, like in the proof of Lemma~\ref{algo-correct}.