Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
We provide an O(n2log 1/δ) time randomized algorithm to check whether a given operation ο × S → S is associative (where n = |S| and δ > 0 is the error probability required of the algorithm). We prove that (for any constant δ) this performance is optimal up to a constant factor, even if the operation is 'cancellative'. No sub-n3 time algorithm was previously known for this task. More generally we give an O(nc) time randomized algorithm to check whether a collection of c-ary operations satisfy any given 'read-once' identity.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Yao Qi, Raja Das, et al.
ISSTA 2009