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=\$, consider
the submonoid of $\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).