Bowen Zhou, Bing Xiang, et al.
SSST 2008
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.
Bowen Zhou, Bing Xiang, et al.
SSST 2008
Israel Cidon, Leonidas Georgiadis, et al.
IEEE/ACM Transactions on Networking
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004