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


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


WORST_CASE(?,O(1))
* Step 1: Sum WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict TRS:
            gcd(x,0()) -> x
            gcd(0(),y) -> y
            gcd(s(x),s(y)) -> if(<(x,y),gcd(s(x),-(y,x)),gcd(-(x,y),s(y)))
        - Signature:
            {gcd/2} / {-/2,0/0,</2,if/3,s/1}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd} and constructors {-,0,<,if,s}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
* Step 2: DependencyPairs WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict TRS:
            gcd(x,0()) -> x
            gcd(0(),y) -> y
            gcd(s(x),s(y)) -> if(<(x,y),gcd(s(x),-(y,x)),gcd(-(x,y),s(y)))
        - Signature:
            {gcd/2} / {-/2,0/0,</2,if/3,s/1}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd} and constructors {-,0,<,if,s}
    + Applied Processor:
        DependencyPairs {dpKind_ = DT}
    + Details:
        We add the following weak dependency pairs:
        
        Strict DPs
          gcd#(x,0()) -> c_1(x)
          gcd#(0(),y) -> c_2(y)
          gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y)))
        Weak DPs
          
        
        and mark the set of starting terms.
* Step 3: UsableRules WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict DPs:
            gcd#(x,0()) -> c_1(x)
            gcd#(0(),y) -> c_2(y)
            gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y)))
        - Strict TRS:
            gcd(x,0()) -> x
            gcd(0(),y) -> y
            gcd(s(x),s(y)) -> if(<(x,y),gcd(s(x),-(y,x)),gcd(-(x,y),s(y)))
        - Signature:
            {gcd/2,gcd#/2} / {-/2,0/0,</2,if/3,s/1,c_1/1,c_2/1,c_3/4}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd#} and constructors {-,0,<,if,s}
    + Applied Processor:
        UsableRules
    + Details:
        We replace rewrite rules by usable rules:
          gcd#(x,0()) -> c_1(x)
          gcd#(0(),y) -> c_2(y)
          gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y)))
* Step 4: SimplifyRHS WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict DPs:
            gcd#(x,0()) -> c_1(x)
            gcd#(0(),y) -> c_2(y)
            gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y)))
        - Signature:
            {gcd/2,gcd#/2} / {-/2,0/0,</2,if/3,s/1,c_1/1,c_2/1,c_3/4}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd#} and constructors {-,0,<,if,s}
    + Applied Processor:
        SimplifyRHS
    + Details:
        Consider the dependency graph
          1:S:gcd#(x,0()) -> c_1(x)
             -->_1 gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y))):3
             -->_1 gcd#(0(),y) -> c_2(y):2
             -->_1 gcd#(x,0()) -> c_1(x):1
          
          2:S:gcd#(0(),y) -> c_2(y)
             -->_1 gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y))):3
             -->_1 gcd#(0(),y) -> c_2(y):2
             -->_1 gcd#(x,0()) -> c_1(x):1
          
          3:S:gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y)))
             -->_2 gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y))):3
             -->_1 gcd#(s(x),s(y)) -> c_3(x,y,gcd#(s(x),-(y,x)),gcd#(-(x,y),s(y))):3
             -->_2 gcd#(0(),y) -> c_2(y):2
             -->_1 gcd#(0(),y) -> c_2(y):2
             -->_2 gcd#(x,0()) -> c_1(x):1
             -->_1 gcd#(x,0()) -> c_1(x):1
          
        Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified:
          gcd#(s(x),s(y)) -> c_3(x,y)
* Step 5: WeightGap WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict DPs:
            gcd#(x,0()) -> c_1(x)
            gcd#(0(),y) -> c_2(y)
            gcd#(s(x),s(y)) -> c_3(x,y)
        - Signature:
            {gcd/2,gcd#/2} / {-/2,0/0,</2,if/3,s/1,c_1/1,c_2/1,c_3/2}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd#} and constructors {-,0,<,if,s}
    + Applied Processor:
        WeightGap {wgDimension = 1, wgDegree = 0, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
    + Details:
        The weightgap principle applies using the following constant growth matrix-interpretation:
          We apply a matrix interpretation of kind constructor based matrix interpretation (containing no more than 0 non-zero interpretation-entries in the diagonal of the component-wise maxima):
          The following argument positions are considered usable:
            none
          
          Following symbols are considered usable:
            all
          TcT has computed the following interpretation:
               p(-) = [0]
               p(0) = [0]
               p(<) = [0]
             p(gcd) = [0]
              p(if) = [0]
               p(s) = [0]
            p(gcd#) = [1]
             p(c_1) = [0]
             p(c_2) = [0]
             p(c_3) = [0]
          
          Following rules are strictly oriented:
              gcd#(x,0()) = [1]     
                          > [0]     
                          = c_1(x)  
          
              gcd#(0(),y) = [1]     
                          > [0]     
                          = c_2(y)  
          
          gcd#(s(x),s(y)) = [1]     
                          > [0]     
                          = c_3(x,y)
          
          
          Following rules are (at-least) weakly oriented:
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 6: EmptyProcessor WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak DPs:
            gcd#(x,0()) -> c_1(x)
            gcd#(0(),y) -> c_2(y)
            gcd#(s(x),s(y)) -> c_3(x,y)
        - Signature:
            {gcd/2,gcd#/2} / {-/2,0/0,</2,if/3,s/1,c_1/1,c_2/1,c_3/2}
        - Obligation:
             runtime complexity wrt. defined symbols {gcd#} and constructors {-,0,<,if,s}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(1))