Lightův test asociativity

Lightův test asociativity je algoritmus z abstraktní algebry. Umožňuje určit, zda je binární operace nad konečnou množinou, jež byla zadána pomocí Cayleyho multiplikativní tabulky, asociativní. Tím lze rozlišit pologrupy, kde operace asociativní je, od grupoidů, jejichž operace asociativní nejsou.

Test je pojmenován po F. W. Lightovi, jenž jej autorům publikace The Algebraic Theory of Semigroups (Algebraická teorie pologrup) představil v roce 1949.

Postup

Základem Lightova testu asociativity je zavedení dvou nových zástupných binárních operací. Pro jednotlivé prvky množiny se pak sestaví Cayleyho tabulky pro tyto dvě operace. +more Pokud jsou poté tabulky ve všech dvojicích takto vzniklých tabulek pro obě zástupné operace shodné, je původní operace asociativní; liší-li se tabulky v nějaké dvojici, původní operace asociativní není.

Reference

Kategorie:Algoritmy Kategorie:Konečné grupy