We consider the following Problem:

  Strict Trs:
    {p(p(b(a(x0)), x1), p(x2, x3)) ->
     p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
  StartTerms: basic terms
  Strategy: innermost

Certificate: YES(?,O(n^1))

Proof:
  We consider the following Problem:
  
    Strict Trs:
      {p(p(b(a(x0)), x1), p(x2, x3)) ->
       p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
    StartTerms: basic terms
    Strategy: innermost
  
  Certificate: YES(?,O(n^1))
  
  Proof:
    We fail transforming the problem using 'weightgap of dimension Nat 2, maximal degree 1, cbits 4'
    
      The weightgap principle does not apply
    
    We try instead 'weightgap of dimension Nat 3, maximal degree 2, cbits 3' on the problem
    
    Strict Trs:
      {p(p(b(a(x0)), x1), p(x2, x3)) ->
       p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
    StartTerms: basic terms
    Strategy: innermost
    
      The weightgap principle applies, where following rules are oriented strictly:
      
      TRS Component:
        {p(p(b(a(x0)), x1), p(x2, x3)) ->
         p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
      
      Interpretation of nonconstant growth:
      -------------------------------------
        The following argument positions are usable:
          Uargs(p) = {2}, Uargs(b) = {}, Uargs(a) = {}
        We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation:
        Interpretation Functions:
         p(x1, x2) = [0 0 1] x1 + [1 1 1] x2 + [0]
                     [0 0 0]      [0 0 0]      [0]
                     [0 1 0]      [0 0 0]      [0]
         b(x1) = [0 0 0] x1 + [0]
                 [0 0 1]      [0]
                 [0 0 0]      [0]
         a(x1) = [0 0 0] x1 + [0]
                 [0 0 0]      [0]
                 [1 1 1]      [1]
      
      The strictly oriented rules are moved into the weak component.
    
    We consider the following Problem:
    
      Weak Trs:
        {p(p(b(a(x0)), x1), p(x2, x3)) ->
         p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
      StartTerms: basic terms
      Strategy: innermost
    
    Certificate: YES(O(1),O(1))
    
    Proof:
      We consider the following Problem:
      
        Weak Trs:
          {p(p(b(a(x0)), x1), p(x2, x3)) ->
           p(p(b(x2), a(a(b(x1)))), p(x3, x0))}
        StartTerms: basic terms
        Strategy: innermost
      
      Certificate: YES(O(1),O(1))
      
      Proof:
        Empty rules are trivially bounded

Hurray, we answered YES(?,O(n^1))