Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
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.
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Nanda Kambhatla
ACL 2004
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering