0 Overview
  - the arena;
    3 operations $(-)^*$, powerset $\mathbb P$, finite powerset $\mathbb F$
  - Rat and Rec on (finitely generated) monoids via different closure processes

    Rat: closing $M\mathbb F$ ``vertically'' in  $M\mathbb P$ 
    under Kleene star (in addition to finite unions and composition)
    for any monoid $M$ (maybe restrict to finitely generated ones);

    This corresponds to the regular (here: rational) expressions

    Rec: closing (``horizontally'') the power-monoids $M\mathbb F=M\mathbb P$
    for $M$ finte under inverse images.

    This corresponts to recognition by automata:
    * given a homomorphism $\tmor{\Sigma^*}hM$ with $M$ finite and a subset
      $T\inc M$, build a complete deterministic automaton with state set $Q=M$,
      initial state $e\in M$ and transition functions the right actions on $M$
      specified by the elements $ah$, $a\in\Sigma$.

    * given a complete deterministic automaton $A=\<Q,q_0,T,\delta\>$, consider
      the submonoid of $<Q,Q>\4Set4$ generated by the image of $\delta$, i.e.,
      by the transition functions $a\delta$, $a\in\Sigma$.

    In particular, the minimal automaton for a language
    $L\inc\Sigma^*$ corresponds uniquely to a homomorphism into a
    ``minimal'' monoid with a suitable subset, the so-called
    ``syntactic monoid''.

    All finite monoids arise a syntactic monoids of some rational language.

  - Kleene's theorem provides a (surprising) connection between these rather
    different closure processes:

    Thm. For finite $\Sigma$, the sets $\Sigma\4Rat$ and $\Sigma\4Rec4$
         coincide.

    In particular, this shows that $\Sigma\4Rat$ is also closed under
    complementation, which justifies extending rational expressions to include
    a complementation operator.

    Since all finite monoids arise as syntactic monoids of some
    rational language, one can try to classify certain ``nice''
    subclasses of $\Sigma\4Rat$ by certain ``nice'' subclasses of
    finite monoids.

    A fist result of this type due to Schützenberger establishes the
    correspondence between ``star-free'' languages (where a rational
    expression w/o Kleene star exists) and aperiodic finite monoids.
    Since then a number of results of this type have been established.

  - Eilenberg identified ``nice'' subclasses of finite monoids by
    closure properties: wrt. homomorphid images (H), submonoids (S) and
    finite products (fP) and established a correspondence of such
    (pseudo)varieties with nice subclasses of languages.

    The problem is how to efficiently specify such varieties
    of finite monoids (also called pseudovarieties).
    
    In universal algebra the notion of ``variety'' specifies ``nice''
    subclasses of classes of not (neccessarily finite) algebras (of a
    given type or signature), by closedness under homomorphic images
    (H), subalgebras (S) and (potentially infinite) products (P).

    Birkhoff (1935) showed that such varieties can be expressed by
    means of sets of equations, i.e., pairs of terms.  Unfortunately,
    for varieties of finite algebras this no longer works.  Equations
    have to be generalized to so-called ``profinite'' equations.  The
    corresponding characterization of varieties of finite algebras is
    due to Reiterman (1980).