/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:
            a(c(d(x))) -> c(x)
            u(b(d(d(x)))) -> b(x)
            v(a(a(x))) -> u(v(x))
            v(a(c(x))) -> u(b(d(x)))
            v(c(x)) -> b(x)
            w(a(a(x))) -> u(w(x))
            w(a(c(x))) -> u(b(d(x)))
            w(c(x)) -> b(x)
        - Signature:
            {a/1,u/1,v/1,w/1} / {b/1,c/1,d/1}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,u,v,w}
    + 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(a) = [1] x1 + [0] 
            p(b) = [1] x1 + [10]
            p(c) = [1] x1 + [11]
            p(d) = [1] x1 + [0] 
            p(u) = [1] x1 + [0] 
            p(v) = [1] x1 + [0] 
            p(w) = [1] x1 + [0] 
          
          Following rules are strictly oriented:
          v(a(c(x))) = [1] x + [11]
                     > [1] x + [10]
                     = u(b(d(x)))  
          
             v(c(x)) = [1] x + [11]
                     > [1] x + [10]
                     = b(x)        
          
          w(a(c(x))) = [1] x + [11]
                     > [1] x + [10]
                     = u(b(d(x)))  
          
             w(c(x)) = [1] x + [11]
                     > [1] x + [10]
                     = b(x)        
          
          
          Following rules are (at-least) weakly oriented:
             a(c(d(x))) =  [1] x + [11]
                        >= [1] x + [11]
                        =  c(x)        
          
          u(b(d(d(x)))) =  [1] x + [10]
                        >= [1] x + [10]
                        =  b(x)        
          
             v(a(a(x))) =  [1] x + [0] 
                        >= [1] x + [0] 
                        =  u(v(x))     
          
             w(a(a(x))) =  [1] x + [0] 
                        >= [1] x + [0] 
                        =  u(w(x))     
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 2: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            a(c(d(x))) -> c(x)
            u(b(d(d(x)))) -> b(x)
            v(a(a(x))) -> u(v(x))
            w(a(a(x))) -> u(w(x))
        - Weak TRS:
            v(a(c(x))) -> u(b(d(x)))
            v(c(x)) -> b(x)
            w(a(c(x))) -> u(b(d(x)))
            w(c(x)) -> b(x)
        - Signature:
            {a/1,u/1,v/1,w/1} / {b/1,c/1,d/1}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,u,v,w}
    + 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(a) = [1] x1 + [0] 
            p(b) = [1] x1 + [4] 
            p(c) = [1] x1 + [12]
            p(d) = [1] x1 + [10]
            p(u) = [1] x1 + [1] 
            p(v) = [1] x1 + [3] 
            p(w) = [1] x1 + [13]
          
          Following rules are strictly oriented:
             a(c(d(x))) = [1] x + [22]
                        > [1] x + [12]
                        = c(x)        
          
          u(b(d(d(x)))) = [1] x + [25]
                        > [1] x + [4] 
                        = b(x)        
          
          
          Following rules are (at-least) weakly oriented:
          v(a(a(x))) =  [1] x + [3] 
                     >= [1] x + [4] 
                     =  u(v(x))     
          
          v(a(c(x))) =  [1] x + [15]
                     >= [1] x + [15]
                     =  u(b(d(x)))  
          
             v(c(x)) =  [1] x + [15]
                     >= [1] x + [4] 
                     =  b(x)        
          
          w(a(a(x))) =  [1] x + [13]
                     >= [1] x + [14]
                     =  u(w(x))     
          
          w(a(c(x))) =  [1] x + [25]
                     >= [1] x + [15]
                     =  u(b(d(x)))  
          
             w(c(x)) =  [1] x + [25]
                     >= [1] x + [4] 
                     =  b(x)        
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 3: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            v(a(a(x))) -> u(v(x))
            w(a(a(x))) -> u(w(x))
        - Weak TRS:
            a(c(d(x))) -> c(x)
            u(b(d(d(x)))) -> b(x)
            v(a(c(x))) -> u(b(d(x)))
            v(c(x)) -> b(x)
            w(a(c(x))) -> u(b(d(x)))
            w(c(x)) -> b(x)
        - Signature:
            {a/1,u/1,v/1,w/1} / {b/1,c/1,d/1}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,u,v,w}
    + 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(a) = [1] x1 + [8] 
            p(b) = [1] x1 + [6] 
            p(c) = [1] x1 + [9] 
            p(d) = [1] x1 + [8] 
            p(u) = [1] x1 + [0] 
            p(v) = [1] x1 + [14]
            p(w) = [1] x1 + [10]
          
          Following rules are strictly oriented:
          v(a(a(x))) = [1] x + [30]
                     > [1] x + [14]
                     = u(v(x))     
          
          w(a(a(x))) = [1] x + [26]
                     > [1] x + [10]
                     = u(w(x))     
          
          
          Following rules are (at-least) weakly oriented:
             a(c(d(x))) =  [1] x + [25]
                        >= [1] x + [9] 
                        =  c(x)        
          
          u(b(d(d(x)))) =  [1] x + [22]
                        >= [1] x + [6] 
                        =  b(x)        
          
             v(a(c(x))) =  [1] x + [31]
                        >= [1] x + [14]
                        =  u(b(d(x)))  
          
                v(c(x)) =  [1] x + [23]
                        >= [1] x + [6] 
                        =  b(x)        
          
             w(a(c(x))) =  [1] x + [27]
                        >= [1] x + [14]
                        =  u(b(d(x)))  
          
                w(c(x)) =  [1] x + [19]
                        >= [1] x + [6] 
                        =  b(x)        
          
        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:
            a(c(d(x))) -> c(x)
            u(b(d(d(x)))) -> b(x)
            v(a(a(x))) -> u(v(x))
            v(a(c(x))) -> u(b(d(x)))
            v(c(x)) -> b(x)
            w(a(a(x))) -> u(w(x))
            w(a(c(x))) -> u(b(d(x)))
            w(c(x)) -> b(x)
        - Signature:
            {a/1,u/1,v/1,w/1} / {b/1,c/1,d/1}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,u,v,w}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^1))