Problem:
 -(x,x) -> 0()
 +(x,y) -> +(y,x)
 +(0(),x) -> x
 +(x,0()) -> x
 +(s(x),y) -> s(+(x,y))
 +(x,s(y)) -> s(+(y,x))
 +(p(x),y) -> p(+(x,y))
 +(x,p(y)) -> p(+(y,x))
 s(p(x)) -> x
 p(s(x)) -> x

Proof:
 sorted: (order)
 0:-(x,x) -> 0()
 1:+(x,y) -> +(y,x)
   +(0(),x) -> x
   +(x,0()) -> x
   +(s(x),y) -> s(+(x,y))
   +(x,s(y)) -> s(+(y,x))
   +(p(x),y) -> p(+(x,y))
   +(x,p(y)) -> p(+(y,x))
   s(p(x)) -> x
   p(s(x)) -> x
 -----
 sorts
   [0>1, 0>3, 2>3]
 sort attachment (non-strict)
   - : 1 x 1 -> 0
   0 : 3
   + : 2 x 2 -> 2
   s : 2 -> 2
   p : 2 -> 2
 -----
 0:-(x,x) -> 0()
   Qed (ToyamaOyamaguchi95Cor22)
 
 
 1:+(x,y) -> +(y,x)
   +(0(),x) -> x
   +(x,0()) -> x
   +(s(x),y) -> s(+(x,y))
   +(x,s(y)) -> s(+(y,x))
   +(p(x),y) -> p(+(x,y))
   +(x,p(y)) -> p(+(y,x))
   s(p(x)) -> x
   p(s(x)) -> x
   AT confluence processor
    Complete TRS T' of input TRS:
    +(0(),x) -> x
    +(x,0()) -> x
    +(s(x),y) -> s(+(x,y))
    +(x,s(y)) -> s(+(y,x))
    +(p(x),y) -> p(+(x,y))
    +(x,p(y)) -> p(+(y,x))
    s(p(x)) -> x
    p(s(x)) -> x
    +(x,y) -> +(y,x)
    
     T' = (P union S) with
    
     TRS P:+(x,y) -> +(y,x)
    
     TRS S:+(0(),x) -> x
           +(x,0()) -> x
           +(s(x),y) -> s(+(x,y))
           +(x,s(y)) -> s(+(y,x))
           +(p(x),y) -> p(+(x,y))
           +(x,p(y)) -> p(+(y,x))
           s(p(x)) -> x
           p(s(x)) -> x
    
    S is linear and P is reversible.
    
     CP(S,S) = 
    0() = 0(), s(y) = s(+(y,0())), p(y) = p(+(y,0())), s(x) = s(+(x,0())), 
    p(x) = p(+(x,0())), s(+(x563,0())) = s(x563), s(+(x565,s(y))) = s(+(y,s(x565))), 
    s(+(x567,p(y))) = p(+(y,s(x567))), s(+(x570,0())) = s(x570), s(+(x572,s(x))) = 
    s(+(x,s(x572))), s(+(x574,p(x))) = p(+(x,s(x574))), p(+(x575,0())) = 
    p(x575), p(+(x577,s(y))) = s(+(y,p(x577))), p(+(x579,p(y))) = p(+(y,p(x579))), 
    p(+(x582,0())) = p(x582), p(+(x584,s(x))) = s(+(x,p(x584))), p(+(x586,p(x))) = 
    p(+(x,p(x586))), +(x587,y) = s(+(p(x587),y)), +(x,x588) = s(+(p(x588),x)), 
    p(x589) = p(x589), +(x590,y) = p(+(s(x590),y)), +(x,x591) = p(+(s(x591),x)), 
    s(x592) = s(x592)
    
     CP(S,P union P^-1) = 
    y = +(y,0()), x = +(x,0()), x = +(0(),x), y = +(0(),y), s(+(x621,y)) = 
    +(y,s(x621)), s(+(x623,x)) = +(x,s(x623)), s(+(x626,x)) = +(s(x626),x), 
    s(+(x628,y)) = +(s(x628),y), p(+(x629,y)) = +(y,p(x629)), p(+(x631,x)) = 
    +(x,p(x631)), p(+(x634,x)) = +(p(x634),x), p(+(x636,y)) = +(p(x636),y)
    
     CP(P union P^-1,S) = 
    +(x,0()) = x, +(0(),x) = x, +(y,s(x)) = s(+(x,y)), +(s(y),x) = s(+(y,x)), 
    +(y,p(x)) = p(+(x,y)), +(p(y),x) = p(+(y,x))
    
    
    We have to check termination of S:
    
    Matrix Interpretation Processor: dim=1
     
     interpretation:
      [p](x0) = x0,
      
      [s](x0) = x0,
      
      [+](x0, x1) = x0 + x1,
      
      [0] = 2
     orientation:
      +(0(),x) = x + 2 >= x = x
      
      +(x,0()) = x + 2 >= x = x
      
      +(s(x),y) = x + y >= x + y = s(+(x,y))
      
      +(x,s(y)) = x + y >= x + y = s(+(y,x))
      
      +(p(x),y) = x + y >= x + y = p(+(x,y))
      
      +(x,p(y)) = x + y >= x + y = p(+(y,x))
      
      s(p(x)) = x >= x = x
      
      p(s(x)) = x >= x = x
     problem:
      +(s(x),y) -> s(+(x,y))
      +(x,s(y)) -> s(+(y,x))
      +(p(x),y) -> p(+(x,y))
      +(x,p(y)) -> p(+(y,x))
      s(p(x)) -> x
      p(s(x)) -> x
     Matrix Interpretation Processor: dim=1
      
      interpretation:
       [p](x0) = x0,
       
       [s](x0) = x0 + 3,
       
       [+](x0, x1) = x0 + x1 + 2
      orientation:
       +(s(x),y) = x + y + 5 >= x + y + 5 = s(+(x,y))
       
       +(x,s(y)) = x + y + 5 >= x + y + 5 = s(+(y,x))
       
       +(p(x),y) = x + y + 2 >= x + y + 2 = p(+(x,y))
       
       +(x,p(y)) = x + y + 2 >= x + y + 2 = p(+(y,x))
       
       s(p(x)) = x + 3 >= x = x
       
       p(s(x)) = x + 3 >= x = x
      problem:
       +(s(x),y) -> s(+(x,y))
       +(x,s(y)) -> s(+(y,x))
       +(p(x),y) -> p(+(x,y))
       +(x,p(y)) -> p(+(y,x))
      Matrix Interpretation Processor: dim=1
       
       interpretation:
        [p](x0) = x0,
        
        [s](x0) = x0 + 2,
        
        [+](x0, x1) = 4x0 + 4x1
       orientation:
        +(s(x),y) = 4x + 4y + 8 >= 4x + 4y + 2 = s(+(x,y))
        
        +(x,s(y)) = 4x + 4y + 8 >= 4x + 4y + 2 = s(+(y,x))
        
        +(p(x),y) = 4x + 4y >= 4x + 4y = p(+(x,y))
        
        +(x,p(y)) = 4x + 4y >= 4x + 4y = p(+(y,x))
       problem:
        +(p(x),y) -> p(+(x,y))
        +(x,p(y)) -> p(+(y,x))
       Matrix Interpretation Processor: dim=1
        
        interpretation:
         [p](x0) = x0 + 4,
         
         [+](x0, x1) = 2x0 + 2x1 + 1
        orientation:
         +(p(x),y) = 2x + 2y + 9 >= 2x + 2y + 5 = p(+(x,y))
         
         +(x,p(y)) = 2x + 2y + 9 >= 2x + 2y + 5 = p(+(y,x))
        problem:
         
        Qed