Report announcement: Taxonomies of finite automata algorithms

I would like to announce the following technical reports (which may be of
interest to the readers of this newsgroup):


        ``A taxonomy of finite automata construction algorithms,'' by Bruce W.
        Watson, Computing Science Note 93/43, Eindhoven University of Technology,
        Eindhoven, The Netherlands, 87 pages (including index), 1993.




        ``A taxonomy of finite automata minimization algorithms,'' by Bruce W.
        Watson, Computing Science Note 93/44, Eindhoven University of Technology,
        Eindhoven, The Netherlands, 23 pages, 1993.






Below, I've included the abstracts and some information on obtaining copies:


ABSTRACT (construction algorithms):
This paper presents a taxonomy of finite automata construction algorithms.
Each algorithm is classified into one of two families: those based upon
the structure of regular expressions, and those based upon the
automata-theoretic work of Myhill and Nerode.


Many of the algorithms appearing in the literature are based upon the
structure of regular expressions. In this paper, we make this term precise
by defining regular expressions as a $\Sigma$-term algebra, and automata
constructions as various $\Sigma$-algebras of automata. Each construction
algorithm is then presented as the unique natural homomorphism from the
$\Sigma$-term algebra of regular expressions to the appropriate
$\Sigma$-algebra of automata. The concept of duality is introduced and
used to derive more practical construction algorithms. In this way, we
successfully present (and relate) algorithms given by Thompson, Berry and
Sethi, McNaughton and Yamada, Glushkov, and Aho, Sethi, and Ullman.
Efficient implementations (including those due to Chang and Paige, and
Br\"uggemann-Klein) are also treated. As a side-effect we derive several
new algorithms.


A pair of impractical, but theoretically interesting, construction
algorithms were presented by Myhill and Nerode. Some encoding techniques
are used to make the algorithms practical --- giving Brzozowski's
algorithm based upon derivatives. DeRemer's algorithm is derived as an
encoding of Brzozowski's algorithm. Two new algorithms, related to
DeRemer's, are derived. Lastly, this family of algorithms is related to
the first family.


In addition to classifying the algorithms, we identify (and abstract from)
the coding tricks and implementation details present in many of the
published algorithms. This paper also presents an introduction to finite
automata, $\Sigma$-algebras, and their properties.
----




ABSTRACT (minimization algorithms):
This paper presents a taxonomy of finite automata minimization algorithms.
Brzozowski's elegant minimization algorithm differs from all other known
minimization algorithms, and is derived separately. All of the remaining
algorithms depend upon computing an equivalence relation on states. We
define the equivalence relation, the partition that it induces, and its
complement. Additionally, some useful properties are derived. It is shown
that the equivalence relation is the greatest fixed point of an equation,
providing a useful characterization of the required computation. We derive
an upperbound on the number of approximation steps required to compute the
fixed point. Algorithms computing the equivalence relation (or the
partition, or its complement) are derived systematically in the same
framework. The algorithms include Hopcroft's, several algorithms from
text-books (including Hopcroft and Ullman's, Wood's, and Aho, Sethi, and
Ullman's), and several new algorithms or variants of existing algorithms.
----






To obtain copies, email a request to me at watson@win.tue.nl, phone me at
+31 40 474319, or write to me at:
        Bruce Watson HG7.39
        Fac. W & I
        Eindhoven University of Technology
        P.O. Box 513
        5600 MB Eindhoven
        The Netherlands


I'm not making these available for ftp for a number of reasons, two of them
being: I would like to be able to distribute an errata list (if needed) to
people, and I don't have easy access to the local ftp server.
If you do get a copy, please feel free to distribute it to anyone (for
free, of course).


The following five versions are available:
        1. PostScript, two pages to one physical page. Saves paper, but can be
              tough on the eyesight.
        2. PostScript, one page to a physical page (normal).
        3. PostScript (600 dpi), one page to a physical page (normal), for use
              with high-resolution printers.
        4. DVI (for those that don't have PostScript printers, but can print DVI).
        5. Paper (discouraged, but if you have no printer or electronic access).




Sincerely,
Bruce.




--
_____________________________________________________________________________
Bruce Watson || favourite oxymoron: "-- rather, it simply
watson@win.tue.nl || complicates our implementation." from
watson@stack.urc.tue.nl || C++ Primer, 2nd ed. (p.501) by S. Lippman
--

Return to the comp.compilers page.
Search the comp.compilers archives again.