\documentclass{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{gastex}
\begin{document}

\title{Experiments with programs for finite automata}
\author{Jean Berstel \and Dominique Perrin}
\maketitle
\tableofcontents

\section{Introduction}
We have described in \cite{LothaireAppCW} a number of minimization
algorithms for finite automata. We discuss here their implementation
and report on the experimentation realized on automata resulting from
dictionnaries in french, which represent lists of large size, allowing
to compare the efficiency of the different methods and
implementations.

\section{A myriad of methods}
Surprisingly, there is plenty of methods which can be used to minimize
a finite automaton. A number of them operate by successive refinements
of a partition of the set of states. This is the case of Moore's and
of Hopcroft's algorithm. A kind of opposite method, working only for a
restricted class of automata works by fusion of equivalent states.
Finally, Bzrozowski's method operates by reversal and determinization
repeated twice.
\subsection{Moore's method}

\subsection{Hopcroft's algorithm}

\subsection{Bzrozowski's algorithm}
Let $\mathfrak{A}=(Q,i,T)$ be a deterministic automaton recognizing a
set $X$. Let $\mathfrak{B}=(Q,T,\{i\})$ be the nondeterministic
automaton obtained by reversing the edges of $\mathfrak{A}=(Q,i,T)$.
Let $\mathfrak{C}$ be the automaton obtained from $\mathfrak{B}$ by
determinization. Then $\mathfrak{C}$ is the minimal automaton
recognizing the reversal of $X$.  This observation can be used
\begin{itemize}
  \item to minimize an automaton by repeating twice the transformation.
  \item to compute the minimal automaton of a set $X$ by starting from
    a deterministic automaton recognizing the reversal $\tilde{X}$ of
    $X$.
\end{itemize}
The complexity is in principle very large since the determinization is
exponential. However, the second variant does not produce an
exponential blow-up if the automaton obtained for $\tilde{X}$ is of
reasonable size.

\subsection{Fusion}
Two states $p,q$ of a deterministic automaton $\mathfrak{A}=(Q,i,T)$
are mergeable if for all $a\in A$, $p.a=q.a$. The merge of two
mergeable states consists in replacing them by a single state. The
fusion algorithm consists in repeatedly identify two mergeable states
and merge them. It is not true that any finite automaton can be
minimized by this method since, for example, the automaton represented
below is not minimal although its tawo states are nor mergeable.
\begin{figure}[htb]
\setlength{\unitlength}{4pt}
\gasset{Nw=4,Nh=4}
\begin{center}
\begin{picture}(25,10)(-5,-4)
\thinlines\small
\node[Nmarks=if](G)(0,0){ $1$}  %[Nmarks=if]
\node[Nmarks=f](D)(20,0){ $2$}  %[Nmarks=f]
\drawedge[curvedepth=3](G,D){ $a$}
\drawedge[curvedepth=3](D,G){ $a$}
\end{picture}
\end{center}
\caption{ A non minimal automaton whose states cannot be merged.}
\label{figGM}
\end{figure}
However, a large class of automata can be minimized by fusion. A
deterministic automaton is called \textit{local} if for any word $x\in
A^*$ there is at most one cycle labeled $x$. For example, an acyclic
automaton is local. Actually, it is proved in \cite{Beal} (see p.56)
that any local automaton can be minimized by fusion.

\section{Results}

The Java class {\tt MinAutomaton} implements a command computing the
minimal automaton of a set of words given in a text file using one of
several possible minimization algorithms.  The minimization algorithms
are contained in the classes implementing the {\tt Minimizer}
interface.  Usage: {\tt java MinAutomaton method file (option)} The
method can be
\begin{itemize}
  \item B (Brzozowski double reverse algorithm).  
  \item F (the fusion algorithm).
  \item N (naive method using {\tt NMinimizer}). This is a naive
    version of Moore's algorithm using a succession of refinements
    without lexicographic sort. Each refinement step runs in
    $O(kn^2)$. The result is a $O(kn^3)$ minimization algorithm. It is
    of course very slow but the space used is reduced to the minimum
    $O(e)$ where $e$ is the number of edges.
  \item Nbis (a variant of the previous using {\tt NbisMinimizer}).  A
    slight improvement on the previous one. The difference is that
    each refinement step runs in $O(knm)$ where $m$ is the current
    number of classes. The resulting minimization method can be
    significantly faster.
  \item H (Hopcroft's algorithm using {\tt HopcroftMinimizer}). This
    algorithm uses a succession of refinements operated by a sequence
    of blocks (the \textit{anvils}) kept in a queue. The result, if
    correctly implemented, is a $O(kn\log n)$ algorithm (see
    \cite{Knuutila2001} for an interesting discussion of this point).
    Its drawbacks are a substantial space required (to store a
    sophisticated data structure) and the dependence on $k$,
    especially because it operates on complete automata.
   \item R (Revuz algorithm using {\tt RMinimizer} to be used only with acyclic
   automata represented as {\tt IDFA}).
 \end{itemize}
   
The option can be {\tt v} (verbose mode).

The files used are all parts of the {\tt delaf} dictionnary. It is a
dictionnary of about 800000 words representing all words in french at
all grammatical forms. A typical part of the {\tt delaf} looks like
\begin{verbatim}
activait
activant
activant
activants
activas
activasse
activassent
activasses
activassiez
activassions
activateur
activateur
activateur biologique
activateur tissulaire du plasminogène
\end{verbatim}
Compound words (like `activateur biologique') are also entries of the
dictionnary.  Some words are repeated because the file is a stripped
version of one associating with each word some information giving its
grammatical category.

The {\tt delafA} is the set of entries beginning with `A' and the {\tt
  delafa} of those beginning with `a'.

The following table gives the result of experiments on these files
using several minimization methods. The first column gives the name of
the file. The second one gives the number of words in the file. The
next one gives the number of nodes of a trie representing the words.
The trie is build using the class {\tt VariableArrayTrie} which
represents the nodes as arrays of variable size of pointers on their
sons.  The column IDFA gives the number of states of an IDFA
equivalent to the trie. Its number of nodes is less because all leaves
are merged into one state (the difference between columns 3 and 4 is
thus equal to the number of distinct words in the dictionary which are
not a prefix of another one).
\begin{figure}[hbt]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|}\hline
           &nbWords&alphabet  &Trie    & IDFA     &Minimal \\ \hline
delafAb.txt&39     &29        &97      & 73       &64      \\ \hline
delafA.txt &731    &   53     &  2526  &   2085   &1202      \\ \hline
delafB.txt &1556   & 58       & 5182   & 4254     &2243     \\ \hline
delafC.txt &2550   & 63       & 9310   & 7742     &4086    \\ \hline   
delafa.txt &60324  & 72       & 175546 &  136886  &36499   \\ \hline
delaf.txt  &802009 &  90      &2203261 & 1683979  &273716      \\ \hline
\end{tabular}
\end{center}
\caption{Parts of the delaf french dictionnary.}
\end{figure}

The table below gives the computation time for each of the files and
the minimization methods.
\begin{figure}[hbt]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}\hline
            &Fusion &Naive  &NaiveBis&Brzozo &Hopcroft&Revuz\\ \hline
delafAb.txt &  33   &30    & 29      &  126  &   58   & 30 \\ \hline
delafA.txt  & 7188  &398   & 281     &   202 &  297   & 116 \\ \hline
delafB.txt  & 31733 &2012  & 1213    &   341 &  693   & 159  \\ \hline
delafC.txt  &       &7427  & 4135    &   507 &  1199  & 210  \\ \hline
delafa.txt  &       &428487   &  6759 & 6922 &        & 2240 \\ \hline
delaf.txt   &       &         &       &      &         & 78550 \\ \hline
\end{tabular}
\end{center}
\caption{Computation time in ms. on a Dell portable}
\end{figure}
\begin{figure}[hbt]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|}\hline
            &Naive  &NaiveBis&Brzozo &Hopcroft&Revuz\\ \hline
delafA.txt & 288   & 211     &       &        &  \\ \hline
delafa.txt &       &325681  & 344149 &        & 2179\\ \hline
delaf.txt  &       &         &       &        & 19135    \\ \hline
\end{tabular}
\end{center}
\caption{Computation time in ms. on Monge}
\end{figure}

\bibliographystyle{plain}

\bibliography{Minimization}



\end{document}
