/export/starexec/sandbox2/solver/bin/starexec_run_tct_dc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(?,O(n^2))
* Step 1: NaturalMI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            average(x,s(s(s(y)))) -> s(average(s(x),y))
            average(0(),0()) -> 0()
            average(0(),s(0())) -> 0()
            average(0(),s(s(0()))) -> s(0())
            average(s(x),y) -> average(x,s(y))
        - Signature:
            {average/2} / {0/0,s/1}
        - Obligation:
             derivational complexity wrt. signature {0,average,s}
    + Applied Processor:
        NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind triangular matrix interpretation:
        
        Following symbols are considered usable:
          all
        TcT has computed the following interpretation:
                p(0) = [0]                  
          p(average) = [1] x1 + [1] x2 + [0]
                p(s) = [1] x1 + [7]         
        
        Following rules are strictly oriented:
         average(x,s(s(s(y)))) = [1] x + [1] y + [21]
                               > [1] x + [1] y + [14]
                               = s(average(s(x),y))  
        
           average(0(),s(0())) = [7]                 
                               > [0]                 
                               = 0()                 
        
        average(0(),s(s(0()))) = [14]                
                               > [7]                 
                               = s(0())              
        
        
        Following rules are (at-least) weakly oriented:
        average(0(),0()) =  [0]                
                         >= [0]                
                         =  0()                
        
         average(s(x),y) =  [1] x + [1] y + [7]
                         >= [1] x + [1] y + [7]
                         =  average(x,s(y))    
        
* Step 2: NaturalMI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            average(0(),0()) -> 0()
            average(s(x),y) -> average(x,s(y))
        - Weak TRS:
            average(x,s(s(s(y)))) -> s(average(s(x),y))
            average(0(),s(0())) -> 0()
            average(0(),s(s(0()))) -> s(0())
        - Signature:
            {average/2} / {0/0,s/1}
        - Obligation:
             derivational complexity wrt. signature {0,average,s}
    + Applied Processor:
        NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind triangular matrix interpretation:
        
        Following symbols are considered usable:
          all
        TcT has computed the following interpretation:
                p(0) = [8]                  
          p(average) = [1] x1 + [1] x2 + [0]
                p(s) = [1] x1 + [0]         
        
        Following rules are strictly oriented:
        average(0(),0()) = [16]
                         > [8] 
                         = 0() 
        
        
        Following rules are (at-least) weakly oriented:
         average(x,s(s(s(y)))) =  [1] x + [1] y + [0]
                               >= [1] x + [1] y + [0]
                               =  s(average(s(x),y)) 
        
           average(0(),s(0())) =  [16]               
                               >= [8]                
                               =  0()                
        
        average(0(),s(s(0()))) =  [16]               
                               >= [8]                
                               =  s(0())             
        
               average(s(x),y) =  [1] x + [1] y + [0]
                               >= [1] x + [1] y + [0]
                               =  average(x,s(y))    
        
* Step 3: NaturalMI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            average(s(x),y) -> average(x,s(y))
        - Weak TRS:
            average(x,s(s(s(y)))) -> s(average(s(x),y))
            average(0(),0()) -> 0()
            average(0(),s(0())) -> 0()
            average(0(),s(s(0()))) -> s(0())
        - Signature:
            {average/2} / {0/0,s/1}
        - Obligation:
             derivational complexity wrt. signature {0,average,s}
    + Applied Processor:
        NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind triangular matrix interpretation:
        
        Following symbols are considered usable:
          all
        TcT has computed the following interpretation:
                p(0) = [0]                      
                       [0]                      
          p(average) = [1 4] x1 + [1 2] x2 + [0]
                       [0 1]      [0 1]      [4]
                p(s) = [1 0] x1 + [0]           
                       [0 1]      [1]           
        
        Following rules are strictly oriented:
        average(s(x),y) = [1 4] x + [1 2] y + [4]
                          [0 1]     [0 1]     [5]
                        > [1 4] x + [1 2] y + [2]
                          [0 1]     [0 1]     [5]
                        = average(x,s(y))        
        
        
        Following rules are (at-least) weakly oriented:
         average(x,s(s(s(y)))) =  [1 4] x + [1 2] y + [6]
                                  [0 1]     [0 1]     [7]
                               >= [1 4] x + [1 2] y + [4]
                                  [0 1]     [0 1]     [6]
                               =  s(average(s(x),y))     
        
              average(0(),0()) =  [0]                    
                                  [4]                    
                               >= [0]                    
                                  [0]                    
                               =  0()                    
        
           average(0(),s(0())) =  [2]                    
                                  [5]                    
                               >= [0]                    
                                  [0]                    
                               =  0()                    
        
        average(0(),s(s(0()))) =  [4]                    
                                  [6]                    
                               >= [0]                    
                                  [1]                    
                               =  s(0())                 
        
* Step 4: EmptyProcessor WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            average(x,s(s(s(y)))) -> s(average(s(x),y))
            average(0(),0()) -> 0()
            average(0(),s(0())) -> 0()
            average(0(),s(s(0()))) -> s(0())
            average(s(x),y) -> average(x,s(y))
        - Signature:
            {average/2} / {0/0,s/1}
        - Obligation:
             derivational complexity wrt. signature {0,average,s}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^2))