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


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


WORST_CASE(?,O(n^2))
* Step 1: NaturalMI.  WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            concat(cons(U,V),Y) -> cons(U,concat(V,Y))
            concat(leaf(),Y) -> Y
            lessleaves(X,leaf()) -> false()
            lessleaves(cons(U,V),cons(W,Z)) -> lessleaves(concat(U,V),concat(W,Z))
            lessleaves(leaf(),cons(W,Z)) -> true()
        - Signature:
            {concat/2,lessleaves/2} / {cons/2,false/0,leaf/0,true/0}
        - Obligation:
             derivational complexity wrt. signature {concat,cons,false,leaf,lessleaves,true}
    + 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(concat) = [1] x1 + [1] x2 + [0]
                p(cons) = [1] x1 + [1] x2 + [8]
               p(false) = [0]                  
                p(leaf) = [8]                  
          p(lessleaves) = [1] x1 + [1] x2 + [8]
                p(true) = [0]                  
        
        Following rules are strictly oriented:
                       concat(leaf(),Y) = [1] Y + [8]                         
                                        > [1] Y + [0]                         
                                        = Y                                   
        
                   lessleaves(X,leaf()) = [1] X + [16]                        
                                        > [0]                                 
                                        = false()                             
        
        lessleaves(cons(U,V),cons(W,Z)) = [1] U + [1] V + [1] W + [1] Z + [24]
                                        > [1] U + [1] V + [1] W + [1] Z + [8] 
                                        = lessleaves(concat(U,V),concat(W,Z)) 
        
           lessleaves(leaf(),cons(W,Z)) = [1] W + [1] Z + [24]                
                                        > [0]                                 
                                        = true()                              
        
        
        Following rules are (at-least) weakly oriented:
        concat(cons(U,V),Y) =  [1] U + [1] V + [1] Y + [8]
                            >= [1] U + [1] V + [1] Y + [8]
                            =  cons(U,concat(V,Y))        
        
* Step 2: NaturalMI.  WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            concat(cons(U,V),Y) -> cons(U,concat(V,Y))
        - Weak TRS:
            concat(leaf(),Y) -> Y
            lessleaves(X,leaf()) -> false()
            lessleaves(cons(U,V),cons(W,Z)) -> lessleaves(concat(U,V),concat(W,Z))
            lessleaves(leaf(),cons(W,Z)) -> true()
        - Signature:
            {concat/2,lessleaves/2} / {cons/2,false/0,leaf/0,true/0}
        - Obligation:
             derivational complexity wrt. signature {concat,cons,false,leaf,lessleaves,true}
    + 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(concat) = [1 1] x1 + [1 0] x2 + [0]
                          [0 1]      [0 1]      [4]
                p(cons) = [1 1] x1 + [1 0] x2 + [0]
                          [0 0]      [0 1]      [1]
               p(false) = [1]                      
                          [0]                      
                p(leaf) = [5]                      
                          [4]                      
          p(lessleaves) = [1 0] x1 + [1 0] x2 + [0]
                          [0 0]      [0 0]      [1]
                p(true) = [5]                      
                          [0]                      
        
        Following rules are strictly oriented:
        concat(cons(U,V),Y) = [1 1] U + [1 1] V + [1 0] Y + [1]
                              [0 0]     [0 1]     [0 1]     [5]
                            > [1 1] U + [1 1] V + [1 0] Y + [0]
                              [0 0]     [0 1]     [0 1]     [5]
                            = cons(U,concat(V,Y))              
        
        
        Following rules are (at-least) weakly oriented:
                       concat(leaf(),Y) =  [1 0] Y + [9]                              
                                           [0 1]     [8]                              
                                        >= [1 0] Y + [0]                              
                                           [0 1]     [0]                              
                                        =  Y                                          
        
                   lessleaves(X,leaf()) =  [1 0] X + [5]                              
                                           [0 0]     [1]                              
                                        >= [1]                                        
                                           [0]                                        
                                        =  false()                                    
        
        lessleaves(cons(U,V),cons(W,Z)) =  [1 1] U + [1 0] V + [1 1] W + [1 0] Z + [0]
                                           [0 0]     [0 0]     [0 0]     [0 0]     [1]
                                        >= [1 1] U + [1 0] V + [1 1] W + [1 0] Z + [0]
                                           [0 0]     [0 0]     [0 0]     [0 0]     [1]
                                        =  lessleaves(concat(U,V),concat(W,Z))        
        
           lessleaves(leaf(),cons(W,Z)) =  [1 1] W + [1 0] Z + [5]                    
                                           [0 0]     [0 0]     [1]                    
                                        >= [5]                                        
                                           [0]                                        
                                        =  true()                                     
        
* Step 3: EmptyProcessor.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            concat(cons(U,V),Y) -> cons(U,concat(V,Y))
            concat(leaf(),Y) -> Y
            lessleaves(X,leaf()) -> false()
            lessleaves(cons(U,V),cons(W,Z)) -> lessleaves(concat(U,V),concat(W,Z))
            lessleaves(leaf(),cons(W,Z)) -> true()
        - Signature:
            {concat/2,lessleaves/2} / {cons/2,false/0,leaf/0,true/0}
        - Obligation:
             derivational complexity wrt. signature {concat,cons,false,leaf,lessleaves,true}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^2))