Mathematische Grundkenntnisse:

Speziell für die Minimierung von Automaten sind folgende Teilbereiche der Mathematik von besonderem Interesse.

Relationen:
Bei binären Relationen handelt es sich stets um eine Menge von Paaren. Der erste Teil eines Paares entstammt dem Definitionsbereich, der zweite dem Wertebereich.

Ist R eine Relation und (a,b) ein Paar in R, dann schreibt man aRb.

Eigenschaften von Relationen:
Eine Relation R auf der Menge M ist:

reflexiv	, wenn aRa für alle a aus M gilt;
irreflexiv	, wenn aRa für alle a aus M falsch ist;
transitiv	, wenn aRc aus aRb und bRc folgt;
symmetrisch	, wenn bRa aus aRb folgt;
asymmetrisch	, wenn aRb impliziert, dass bRa nicht gilt.

Äquivalenzrelationen:

Eine Relation R, die reflexiv, symmetrisch und transitiv ist, heisst Äquivalenzrelation.