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


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


WORST_CASE(?,O(n^1))
* Step 1: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            app(cons(X),YS) -> cons(X)
            app(nil(),YS) -> YS
            from(X) -> cons(X)
            prefix(L) -> cons(nil())
            zWadr(XS,nil()) -> nil()
            zWadr(cons(X),cons(Y)) -> cons(app(Y,cons(X)))
            zWadr(nil(),YS) -> nil()
        - Signature:
            {app/2,from/1,prefix/1,zWadr/2} / {cons/1,nil/0}
        - Obligation:
            innermost derivational complexity wrt. signature {app,cons,from,nil,prefix,zWadr}
    + Applied Processor:
        WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = NoUArgs, wgOn = WgOnAny}
    + Details:
        The weightgap principle applies using the following nonconstant growth matrix-interpretation:
          We apply a matrix interpretation of kind triangular matrix interpretation:
          
          Following symbols are considered usable:
            all
          TcT has computed the following interpretation:
               p(app) = [1] x1 + [1] x2 + [10]
              p(cons) = [1] x1 + [0]          
              p(from) = [1] x1 + [0]          
               p(nil) = [0]                   
            p(prefix) = [1] x1 + [0]          
             p(zWadr) = [1] x1 + [1] x2 + [11]
          
          Following rules are strictly oriented:
                 app(cons(X),YS) = [1] X + [1] YS + [10]
                                 > [1] X + [0]          
                                 = cons(X)              
          
                   app(nil(),YS) = [1] YS + [10]        
                                 > [1] YS + [0]         
                                 = YS                   
          
                 zWadr(XS,nil()) = [1] XS + [11]        
                                 > [0]                  
                                 = nil()                
          
          zWadr(cons(X),cons(Y)) = [1] X + [1] Y + [11] 
                                 > [1] X + [1] Y + [10] 
                                 = cons(app(Y,cons(X))) 
          
                 zWadr(nil(),YS) = [1] YS + [11]        
                                 > [0]                  
                                 = nil()                
          
          
          Following rules are (at-least) weakly oriented:
            from(X) =  [1] X + [0]
                    >= [1] X + [0]
                    =  cons(X)    
          
          prefix(L) =  [1] L + [0]
                    >= [0]        
                    =  cons(nil())
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 2: NaturalMI.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            from(X) -> cons(X)
            prefix(L) -> cons(nil())
        - Weak TRS:
            app(cons(X),YS) -> cons(X)
            app(nil(),YS) -> YS
            zWadr(XS,nil()) -> nil()
            zWadr(cons(X),cons(Y)) -> cons(app(Y,cons(X)))
            zWadr(nil(),YS) -> nil()
        - Signature:
            {app/2,from/1,prefix/1,zWadr/2} / {cons/1,nil/0}
        - Obligation:
            innermost derivational complexity wrt. signature {app,cons,from,nil,prefix,zWadr}
    + 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(app) = [1] x1 + [1] x2 + [0]
            p(cons) = [1] x1 + [0]         
            p(from) = [1] x1 + [8]         
             p(nil) = [0]                  
          p(prefix) = [1] x1 + [0]         
           p(zWadr) = [1] x1 + [1] x2 + [0]
        
        Following rules are strictly oriented:
        from(X) = [1] X + [8]
                > [1] X + [0]
                = cons(X)    
        
        
        Following rules are (at-least) weakly oriented:
               app(cons(X),YS) =  [1] X + [1] YS + [0]
                               >= [1] X + [0]         
                               =  cons(X)             
        
                 app(nil(),YS) =  [1] YS + [0]        
                               >= [1] YS + [0]        
                               =  YS                  
        
                     prefix(L) =  [1] L + [0]         
                               >= [0]                 
                               =  cons(nil())         
        
               zWadr(XS,nil()) =  [1] XS + [0]        
                               >= [0]                 
                               =  nil()               
        
        zWadr(cons(X),cons(Y)) =  [1] X + [1] Y + [0] 
                               >= [1] X + [1] Y + [0] 
                               =  cons(app(Y,cons(X)))
        
               zWadr(nil(),YS) =  [1] YS + [0]        
                               >= [0]                 
                               =  nil()               
        
* Step 3: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            prefix(L) -> cons(nil())
        - Weak TRS:
            app(cons(X),YS) -> cons(X)
            app(nil(),YS) -> YS
            from(X) -> cons(X)
            zWadr(XS,nil()) -> nil()
            zWadr(cons(X),cons(Y)) -> cons(app(Y,cons(X)))
            zWadr(nil(),YS) -> nil()
        - Signature:
            {app/2,from/1,prefix/1,zWadr/2} / {cons/1,nil/0}
        - Obligation:
            innermost derivational complexity wrt. signature {app,cons,from,nil,prefix,zWadr}
    + Applied Processor:
        WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = NoUArgs, wgOn = WgOnAny}
    + Details:
        The weightgap principle applies using the following nonconstant growth matrix-interpretation:
          We apply a matrix interpretation of kind triangular matrix interpretation:
          
          Following symbols are considered usable:
            all
          TcT has computed the following interpretation:
               p(app) = [1] x1 + [1] x2 + [0]
              p(cons) = [1] x1 + [5]         
              p(from) = [1] x1 + [5]         
               p(nil) = [2]                  
            p(prefix) = [1] x1 + [9]         
             p(zWadr) = [1] x1 + [1] x2 + [2]
          
          Following rules are strictly oriented:
          prefix(L) = [1] L + [9]
                    > [7]        
                    = cons(nil())
          
          
          Following rules are (at-least) weakly oriented:
                 app(cons(X),YS) =  [1] X + [1] YS + [5]
                                 >= [1] X + [5]         
                                 =  cons(X)             
          
                   app(nil(),YS) =  [1] YS + [2]        
                                 >= [1] YS + [0]        
                                 =  YS                  
          
                         from(X) =  [1] X + [5]         
                                 >= [1] X + [5]         
                                 =  cons(X)             
          
                 zWadr(XS,nil()) =  [1] XS + [4]        
                                 >= [2]                 
                                 =  nil()               
          
          zWadr(cons(X),cons(Y)) =  [1] X + [1] Y + [12]
                                 >= [1] X + [1] Y + [10]
                                 =  cons(app(Y,cons(X)))
          
                 zWadr(nil(),YS) =  [1] YS + [4]        
                                 >= [2]                 
                                 =  nil()               
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 4: EmptyProcessor.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            app(cons(X),YS) -> cons(X)
            app(nil(),YS) -> YS
            from(X) -> cons(X)
            prefix(L) -> cons(nil())
            zWadr(XS,nil()) -> nil()
            zWadr(cons(X),cons(Y)) -> cons(app(Y,cons(X)))
            zWadr(nil(),YS) -> nil()
        - Signature:
            {app/2,from/1,prefix/1,zWadr/2} / {cons/1,nil/0}
        - Obligation:
            innermost derivational complexity wrt. signature {app,cons,from,nil,prefix,zWadr}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^1))