\begin{procedure}[p]
  \dontprintsemicolon
  \SetKwFunction{EstProb}{EstimateProb}
  \SetKwFunction{CompleteGraph}{CompleteGraph}  
  \SetKwFunction{Fusion}{Fusion} 
  \SetKwFunction{ComputeSampleSize}{ComputeSampleSize}

  \AlgData{ alphabet: $\Sigma$, distinguishability:  $\mu$,\\ 
    bound on number of states: $n$, \\
    length bound from any state L, \\
%    \texttt{overall sample size:} $m$, \\
    confidence and precision parameters: $\delta$, $\epsilon$} 
  \AlgResult{a PDFA}
  calculate  $N$, $m_0$  and $\gamma_{min}$ from input parameters\;    %N $\leftarrow$ $\frac{m}{n(|\Sigma|+2)}$ \;
  S $\leftarrow$ a multiset from a new sample of N strings \;
  G = (V,E) $\leftarrow$ (\{$v_0$\},\{\}) \;
  $S_{v_0} \leftarrow S$ \;
  \While{$G$ has changed}{
    $G \leftarrow $ AddStructure(G)\;
}

$G \leftarrow $ CompleteGraph($G$)\;
$A \leftarrow $ ConstructPDFA($G$, $\gamma_{min}$)\;
\KwRet($A$)\;
\caption{LearnPDFA($\Sigma$, $\mu$,$n$, $L$, $\delta$, $\epsilon$) \label{algo}}
\end{procedure}





\label{algo2}

\begin{procedure}[p]
  \dontprintsemicolon

  \AlgData{graph $G = (V,E, u_0)$, a sample size $N$, threshold $m_0$, distinguishability $\mu$}
  \AlgResult{graph $G$}
    C $\leftarrow$ ConstructCandidateNodes(G, N) \;
    \ForEach{ candidate node $(u,\sigma)$ with multiset $S_{u,\sigma})$ in C}{     
       \If{$|S_{u,\sigma}| \geq m_0$ }{
       found $\leftarrow$ false \;
       \ForEach { node $v$ in $V$}{
         \If{\textbf{not} found \textbf{and} 
           $L_{\infty}$($\hat{S_v}$, $\hat{S}_{u,\sigma}$) $ < \mu/2$}{
           // add a new edge \;
           $E \leftarrow E \cup  (u,\sigma,v )$ \;
           found $\leftarrow$ true \;
         }
       }



        \If{not found}{
          // add a new node and an edge to it \;
            $V \leftarrow V \cup \{v'\}$ \;
          $S_{v'} \leftarrow  S_{u,\sigma}$ \;
          $ E \leftarrow E \cup (u,\sigma,v')$  \;
}}}

\KwRet{updated G}
\caption{AddStructure(G,$N$,$m_0$,$\mu$)}
\end{procedure}




\begin{procedure}[p]
  \dontprintsemicolon

  \AlgData{graph $G = (V,E, u_0)$}
  \AlgResult{$G$}
  \If{for every node $u$ in $V$ and every letter $\sigma$, 
    there is a $v$ in $V$ such that the edge $(u,\sigma,v)$ is in $E$ }{
    \KwRet{G}
  }
   \Else{

     $V \leftarrow V \cup u_{\infty}$ \;
     \ForEach{ $\sigma \in \Sigma$}{
       \ForEach{ $u \in V$}{
        \If{there is no $v$ in $V$ such that $(u,\sigma, v) \in E$}{
          $E \leftarrow E \cup (u, \sigma, u_{\infty})$ 
        }
       }
     }
     \KwRet{updated G}
   }
    \caption{CompleteGraph(G)}
\end{procedure}


\begin{procedure}[p]
  \dontprintsemicolon

  \AlgData{ a graph $G = (V,E, u_0)$, a smoothing constant $\gamma_{min}$}
     \AlgResult{a PDFA $A$}
     $Q \leftarrow {q_f}$ \;
     $\alpha \leftarrow  (1 - (|\Sigma|+1)\gamma_{min})$  \;
       \ForEach{ $u$ in $V$}{
         Add a state $q_u$ to $Q$ \;
}
       \ForEach{  $u$ in $V$}{
         $m \leftarrow  | S_u|$ \;
         \ForEach{  $\sigma$ in $\Sigma$}{
           Find edge $(u, \sigma, v)$ in $E$ \;
           $\tau(q_u, \sigma) \leftarrow v$ \;
           $\gamma(q_u, \sigma) \leftarrow \gamma_{min}  
+  (\alpha S_u(\sigma)/|S_u|)$  \;

}

         $\tau(q_u, \zeta) \leftarrow q_f$ \;
         $\gamma(q_u, \zeta) \leftarrow \gamma_{min}  +  (\alpha S_u(\lambda)/|S_u|)$  \;
}
$A \leftarrow (Q, \Sigma, q_{u_0}, q_f, \zeta, \tau, \gamma) $\;
\KwRet(A) \;

\caption{ConstructPDFA(G,$\gamma_{min}$)}
\end{procedure}

 

\begin{procedure}[p]
  \dontprintsemicolon

  \AlgData{ a graph $G = (V,E, u_0)$, a sample size $N$}

  \AlgResult{a set of candidate nodes}
  initialise $C \leftarrow\{\}$ \;
   \ForEach{ $u$ in $V$}{
   \ForEach{$\sigma$ in $\Sigma$}{
   \If{there is not an edge in $E$  from $u$ labelled with $\sigma$}
      {
        $C \leftarrow C \cup (u, \sigma, \{\}_{multi})$  
      }
   }
   }
\For{$i$ = 1 to $N$}{
  $s \leftarrow$ new sample string \;
  $u \leftarrow u_0$ \;
  \While{$|s| > 0$}{
    $\sigma \leftarrow $  first letter of $s$ \;
    \If{there is an edge $(u, \sigma, v)$ in $E$}{
      $u \leftarrow v$ \;
      $s \leftarrow s$ with the first letter removed \;
    }
    \Else{
      Find candidate node in $C$ of form $(u, \sigma, S_{u,\sigma})$ \;
      $ S_{u,\sigma}  \leftarrow S_{u,\sigma} \cup s$ \;
      $s \leftarrow \lambda$ \;
    }
  }
 }
  \KwRet{C} \;
\caption{ConstructCandidateNodes(G,N) \label{algo:cn}}
\end{procedure}
















%
%
%
%
% End of program description
%
%
%
%

