YES(?,O(n^2))
11.28/6.45	YES(?,O(n^2))
11.28/6.46	
11.28/6.46	Problem:
11.28/6.46	 average(s(x),y) -> average(x,s(y))
11.28/6.46	 average(x,s(s(s(y)))) -> s(average(s(x),y))
11.28/6.46	 average(0(),0()) -> 0()
11.28/6.46	 average(0(),s(0())) -> 0()
11.28/6.46	 average(0(),s(s(0()))) -> s(0())
11.28/6.46	
11.28/6.46	Proof:
11.28/6.46	 Complexity Transformation Processor:
11.28/6.46	  strict:
11.28/6.46	   average(s(x),y) -> average(x,s(y))
11.28/6.46	   average(x,s(s(s(y)))) -> s(average(s(x),y))
11.28/6.46	   average(0(),0()) -> 0()
11.28/6.46	   average(0(),s(0())) -> 0()
11.28/6.46	   average(0(),s(s(0()))) -> s(0())
11.28/6.46	  weak:
11.28/6.46	   
11.28/6.46	  Matrix Interpretation Processor: dim=1
11.28/6.46	   
11.28/6.46	   max_matrix:
11.28/6.46	    1
11.28/6.46	   interpretation:
11.28/6.46	    [0] = 2,
11.28/6.46	    
11.28/6.46	    [average](x0, x1) = x0 + x1 + 133,
11.28/6.46	    
11.28/6.46	    [s](x0) = x0 + 2
11.28/6.46	   orientation:
11.28/6.46	    average(s(x),y) = x + y + 135 >= x + y + 135 = average(x,s(y))
11.28/6.46	    
11.28/6.46	    average(x,s(s(s(y)))) = x + y + 139 >= x + y + 137 = s(average(s(x),y))
11.28/6.46	    
11.28/6.46	    average(0(),0()) = 137 >= 2 = 0()
11.28/6.46	    
11.28/6.46	    average(0(),s(0())) = 139 >= 2 = 0()
11.28/6.46	    
11.28/6.46	    average(0(),s(s(0()))) = 141 >= 4 = s(0())
11.28/6.46	   problem:
11.28/6.46	    strict:
11.28/6.46	     average(s(x),y) -> average(x,s(y))
11.28/6.46	    weak:
11.28/6.46	     average(x,s(s(s(y)))) -> s(average(s(x),y))
11.28/6.46	     average(0(),0()) -> 0()
11.28/6.46	     average(0(),s(0())) -> 0()
11.28/6.46	     average(0(),s(s(0()))) -> s(0())
11.28/6.46	   Matrix Interpretation Processor: dim=4
11.28/6.46	    
11.28/6.46	    max_matrix:
11.28/6.46	     [1 1 1 1]
11.28/6.46	     [0 1 1 1]
11.28/6.46	     [0 0 0 1]
11.28/6.46	     [0 0 0 0]
11.28/6.46	    interpretation:
11.28/6.46	           [0]
11.28/6.46	           [0]
11.28/6.46	     [0] = [0]
11.28/6.46	           [0],
11.28/6.46	     
11.28/6.46	                         [1 1 1 1]     [1 0 0 0]  
11.28/6.46	                         [0 1 1 1]     [0 1 1 1]  
11.28/6.46	     [average](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1
11.28/6.46	                         [0 0 0 0]     [0 0 0 0]  ,
11.28/6.46	     
11.28/6.46	               [1 0 0 0]     [1]
11.28/6.46	               [0 1 1 0]     [1]
11.28/6.46	     [s](x0) = [0 0 0 1]x0 + [0]
11.28/6.46	               [0 0 0 0]     [0]
11.28/6.46	    orientation:
11.28/6.46	                       [1 1 1 1]    [1 0 0 0]    [2]    [1 1 1 1]    [1 0 0 0]    [1]                  
11.28/6.46	                       [0 1 1 1]    [0 1 1 1]    [1]    [0 1 1 1]    [0 1 1 1]    [1]                  
11.28/6.46	     average(s(x),y) = [0 0 0 0]x + [0 0 0 0]y + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0] = average(x,s(y))
11.28/6.46	                       [0 0 0 0]    [0 0 0 0]    [0]    [0 0 0 0]    [0 0 0 0]    [0]                  
11.28/6.46	     
11.28/6.46	                             [1 1 1 1]    [1 0 0 0]    [3]    [1 1 1 1]    [1 0 0 0]    [3]                     
11.28/6.46	                             [0 1 1 1]    [0 1 1 1]    [3]    [0 1 1 1]    [0 1 1 1]    [2]                     
11.28/6.46	     average(x,s(s(s(y)))) = [0 0 0 0]x + [0 0 0 0]y + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0] = s(average(s(x),y))
11.28/6.46	                             [0 0 0 0]    [0 0 0 0]    [0]    [0 0 0 0]    [0 0 0 0]    [0]                     
11.28/6.46	     
11.28/6.46	                        [0]    [0]      
11.28/6.46	                        [0]    [0]      
11.28/6.46	     average(0(),0()) = [0] >= [0] = 0()
11.28/6.46	                        [0]    [0]      
11.28/6.46	     
11.28/6.46	                           [1]    [0]      
11.28/6.46	                           [1]    [0]      
11.28/6.46	     average(0(),s(0())) = [0] >= [0] = 0()
11.28/6.46	                           [0]    [0]      
11.28/6.46	     
11.28/6.46	                              [2]    [1]         
11.28/6.46	                              [2]    [1]         
11.28/6.46	     average(0(),s(s(0()))) = [0] >= [0] = s(0())
11.28/6.46	                              [0]    [0]         
11.28/6.46	    problem:
11.28/6.46	     strict:
11.28/6.46	      
11.28/6.46	     weak:
11.28/6.46	      average(s(x),y) -> average(x,s(y))
11.28/6.46	      average(x,s(s(s(y)))) -> s(average(s(x),y))
11.28/6.46	      average(0(),0()) -> 0()
11.28/6.46	      average(0(),s(0())) -> 0()
11.28/6.46	      average(0(),s(s(0()))) -> s(0())
11.28/6.46	    Qed
11.28/6.46	EOF