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

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. 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

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)