/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:
            a(x1) -> c(b(x1))
            b(b(x1)) -> a(c(x1))
            b(c(x1)) -> a(x1)
            c(c(c(x1))) -> b(x1)
        - Signature:
            {a/1,b/1,c/1} / {}
        - Obligation:
             derivational complexity wrt. signature {a,b,c}
    + 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(a) = [1] x1 + [26]
          p(b) = [1] x1 + [18]
          p(c) = [1] x1 + [8] 
        
        Following rules are strictly oriented:
           b(b(x1)) = [1] x1 + [36]
                    > [1] x1 + [34]
                    = a(c(x1))     
        
        c(c(c(x1))) = [1] x1 + [24]
                    > [1] x1 + [18]
                    = b(x1)        
        
        
        Following rules are (at-least) weakly oriented:
           a(x1) =  [1] x1 + [26]
                 >= [1] x1 + [26]
                 =  c(b(x1))     
        
        b(c(x1)) =  [1] x1 + [26]
                 >= [1] x1 + [26]
                 =  a(x1)        
        
* Step 2: NaturalMI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            a(x1) -> c(b(x1))
            b(c(x1)) -> a(x1)
        - Weak TRS:
            b(b(x1)) -> a(c(x1))
            c(c(c(x1))) -> b(x1)
        - Signature:
            {a/1,b/1,c/1} / {}
        - Obligation:
             derivational complexity wrt. signature {a,b,c}
    + 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(a) = [1 19] x1 + [254]
                 [0  1]      [73] 
          p(b) = [1 14] x1 + [0]  
                 [0  1]      [50] 
          p(c) = [1 5] x1 + [4]   
                 [0 1]      [23]  
        
        Following rules are strictly oriented:
        b(c(x1)) = [1 19] x1 + [326]
                   [0  1]      [73] 
                 > [1 19] x1 + [254]
                   [0  1]      [73] 
                 = a(x1)            
        
        
        Following rules are (at-least) weakly oriented:
              a(x1) =  [1 19] x1 + [254]
                       [0  1]      [73] 
                    >= [1 19] x1 + [254]
                       [0  1]      [73] 
                    =  c(b(x1))         
        
           b(b(x1)) =  [1 28] x1 + [700]
                       [0  1]      [100]
                    >= [1 24] x1 + [695]
                       [0  1]      [96] 
                    =  a(c(x1))         
        
        c(c(c(x1))) =  [1 15] x1 + [357]
                       [0  1]      [69] 
                    >= [1 14] x1 + [0]  
                       [0  1]      [50] 
                    =  b(x1)            
        
* Step 3: NaturalMI WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            a(x1) -> c(b(x1))
        - Weak TRS:
            b(b(x1)) -> a(c(x1))
            b(c(x1)) -> a(x1)
            c(c(c(x1))) -> b(x1)
        - Signature:
            {a/1,b/1,c/1} / {}
        - Obligation:
             derivational complexity wrt. signature {a,b,c}
    + 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(a) = [1 180] x1 + [250]
                 [0   1]      [3]  
          p(b) = [1 132] x1 + [112]
                 [0   1]      [2]  
          p(c) = [1 48] x1 + [6]   
                 [0  1]      [1]   
        
        Following rules are strictly oriented:
        a(x1) = [1 180] x1 + [250]
                [0   1]      [3]  
              > [1 180] x1 + [214]
                [0   1]      [3]  
              = c(b(x1))          
        
        
        Following rules are (at-least) weakly oriented:
           b(b(x1)) =  [1 264] x1 + [488]
                       [0   1]      [4]  
                    >= [1 228] x1 + [436]
                       [0   1]      [4]  
                    =  a(c(x1))          
        
           b(c(x1)) =  [1 180] x1 + [250]
                       [0   1]      [3]  
                    >= [1 180] x1 + [250]
                       [0   1]      [3]  
                    =  a(x1)             
        
        c(c(c(x1))) =  [1 144] x1 + [162]
                       [0   1]      [3]  
                    >= [1 132] x1 + [112]
                       [0   1]      [2]  
                    =  b(x1)             
        
* Step 4: EmptyProcessor WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            a(x1) -> c(b(x1))
            b(b(x1)) -> a(c(x1))
            b(c(x1)) -> a(x1)
            c(c(c(x1))) -> b(x1)
        - Signature:
            {a/1,b/1,c/1} / {}
        - Obligation:
             derivational complexity wrt. signature {a,b,c}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^2))