class_docstr: A class implementing rewriting systems for `FpGroup`s.
  
  References
  ==========
  .. [1] Epstein, D., Holt, D. and Rees, S. (1991).
         The use of Knuth-Bendix methods to solve the word problem in automatic groups.
         Journal of Symbolic Computation, 12(4-5), pp.397-414.
  
  .. [2] GAP's Manual on its KBMAG package
         https://www.gap-system.org/Manuals/pkg/kbmag-1.5.3/doc/manual.pdf
class_docstr_tok: ["A","class","implementing","rewriting","systems","for","`","FpGroup","`","s",".","References","==========","..","[","1","]","Epstein",",","D.",",","Holt",",","D.","and","Rees",",","S.","(","1991",")",".","The","use","of","Knuth-Bendix","methods","to","solve","the","word","problem","in","automatic","groups",".","Journal","of","Symbolic","Computation",",","12","(","4-5",")",",","pp.397-414",".","..","[","2","]","GAP","'s","Manual","on","its","KBMAG","package","https",":","\/\/www.gap-system.org\/Manuals\/pkg\/kbmag-1.5.3\/doc\/manual.pdf"]
code: def add_rule(self, w1, w2, check=False):
      new_keys = set()
  
      if w1 == w2:
          return new_keys
  
      if w1 < w2:
          w1, w2 = w2, w1
  
      if (w1, w2) in self.rules_cache:
          return new_keys
      self.rules_cache.append((w1, w2))
  
      s1, s2 = w1, w2
  
      # The following is the equivalent of checking
      # s1 for overlaps with the implicit reductions
      # {g*g**-1 -> <identity>} and {g**-1*g -> <identity>}
      # for any generator g without installing the
      # redundant rules that would result from processing
      # the overlaps. See [1], Section 3 for details.
  
      if len(s1) - len(s2) < 3:
          if s1 not in self.rules:
              new_keys.add(s1)
              if not check:
                  self._add_rule(s1, s2)
          if s2**-1 > s1**-1 and s2**-1 not in self.rules:
              new_keys.add(s2**-1)
              if not check:
                  self._add_rule(s2**-1, s1**-1)
  
      # overlaps on the right
      while len(s1) - len(s2) > -1:
          g = s1[len(s1) - 1]
          s1 = s1.subword(0, len(s1) - 1)
          s2 = s2 * g**-1
          if len(s1) - len(s2) < 0:
              if s2 not in self.rules:
                  if not check:
                      self._add_rule(s2, s1)
                  new_keys.add(s2)
          elif len(s1) - len(s2) < 3:
              new = self.add_rule(s1, s2, check)
              new_keys.update(new)
  
      # overlaps on the left
      while len(w1) - len(w2) > -1:
          g = w1[0]
          w1 = w1.subword(1, len(w1))
          w2 = g**-1 * w2
          if len(w1) - len(w2) < 0:
              if w2 not in self.rules:
                  if not check:
                      self._add_rule(w2, w1)
                  new_keys.add(w2)
          elif len(w1) - len(w2) < 3:
              new = self.add_rule(w1, w2, check)
              new_keys.update(new)
  
      return new_keys
  
file_path: sympy/sympy/combinatorics/rewritingsystem.py
imports: from collections import deque
  from sympy.combinatorics.rewritingsystem_fsm import StateMachine
label_desc: Use image node_id 6 for calling the RewritingSystem obj's underlying member method code with example usage: obj.add_rule(w1, w2, check) and returns: new_keys, new_keys, new_keys