Knuth–Bendix algorithm (Coset Enumeration Coset Enumeration)
Jump to navigation
Jump to search
Time Complexity
$O({1.5}^n n^{2} logn)$
Space Complexity
$O(ng)$??? words
(Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g)))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM?
Year
1970
Reference
https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf