Lightův test asociativity

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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.[1]

Postup[editovat | editovat zdroj]

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. 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[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Light's associativity test na anglické Wikipedii.

  1. CLIFFORD, Alfred Hoblitzelle; PRESTON, Gordon Bamford. The Algebraic Theory of Semigroups. Díl 1. [s.l.]: American Mathematical Society, 1961. 224 s. ISBN 0821873881. Kapitola Light's associativity test, s. 7. (anglicky)