6. Princíp výberu minimálneho súboru tried zlučiteľnosti

Maximálne triedy zlučiteľnosti, zostavené pomocou procedúry pre zostavenie maximálnych tried zlučiteľnosti, tvoria úplný prípustný súbor tried zlučiteľnosti. Tento súbor však nie je pri neúplne určených automatoch minimálny. 
Zostaviť minimálny súbor je náročná úloha. Bola navrhnutá metóda, ktorá sa zakladá na hľadaní minimálneho pokrytia boolovskej funkcie pomocou prostých implikantov. Zavádzajú sa prosté triedy zlučiteľnosti a vychádza sa z toho, že aspoň jeden minimálny súbor sa skladá z týchto prostých tried. Metódu možno rozdeliť na dve etapy:

  1. Vyhľadanie množiny všetkých prostých tried zlučiteľnosti.
  2. Výber minimálneho súboru z tejto množiny.
Množina implikovaných tried zlučiteľnosti (implikovaná množina) Pi = {Ci1,...,Cim} pre danú triedu zlučiteľnosti Ci, automatu M = (X, S, Y, d, l) sa nazýva množina všetkých tried zlučiteľnosti implikovaných triedou Ci pri jednotlivých vstupoch automatu, ak spĺňa nasledujúce podmienky:
  1. Cij obsahuje viac ako jeden stav,
  2. Cij nie je podmnožinou Ci, 
  3. Cij nie je podmnožinou Cik, ak CikÎPi a jąi.
(viď príklad) Trieda zlučiteľnosti Ci daného automatu M sa nazýva prostá vtedy a len vtedy, ak neexistuje žiadna iná trieda zlučiteľnosti Cj automatu M taká, že platí:

Ci Í Cj a Pi Í Pj

kde Pi, Pj sú implikované množiny pre triedy Ci a Cj. 
Prosté triedy sú práve tie triedy, ktoré nie sú vylúčené žiadnou inou triedou a predstavujú teda vhodných kandidátov na zaradenie do zostavovaného súboru. Idea výberu minimálneho súboru vychádza z nasledujúcej vety:
Najmenej jeden minimálny súbor obsahuje len prosté triedy. Nie všetky minimálne súbory obsahujú len prosté triedy a nie všetky úplné a prípustné súbory zostavené z prostých tried sú minimálne.