/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: NaturalMI.  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:
        NaturalMI {miDimension = 1, miDegree = 0, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + Details:
        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) = [3]                  
             p(<) = [0]                  
           p(gcd) = [0]                  
            p(if) = [0]                  
             p(s) = [0]                  
          p(gcd#) = [8] x1 + [8] x2 + [1]
           p(c_1) = [1] x1 + [0]         
           p(c_2) = [1] x1 + [8]         
           p(c_3) = [1]                  
        
        Following rules are strictly oriented:
        gcd#(x,0()) = [8] x + [25]
                    > [1] x + [0] 
                    = c_1(x)      
        
        gcd#(0(),y) = [8] y + [25]
                    > [1] y + [8] 
                    = c_2(y)      
        
        
        Following rules are (at-least) weakly oriented:
        gcd#(s(x),s(y)) =  [1]     
                        >= [1]     
                        =  c_3(x,y)
        
* Step 6: NaturalMI.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict DPs:
            gcd#(s(x),s(y)) -> c_3(x,y)
        - Weak DPs:
            gcd#(x,0()) -> c_1(x)
            gcd#(0(),y) -> c_2(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:
        NaturalMI {miDimension = 1, miDegree = 0, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules}
    + Details:
        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) = [7]         
          p(gcd#) = [1] x2 + [0]
           p(c_1) = [0]         
           p(c_2) = [1] x1 + [0]
           p(c_3) = [3]         
        
        Following rules are strictly oriented:
        gcd#(s(x),s(y)) = [7]     
                        > [3]     
                        = c_3(x,y)
        
        
        Following rules are (at-least) weakly oriented:
        gcd#(x,0()) =  [0]        
                    >= [0]        
                    =  c_1(x)     
        
        gcd#(0(),y) =  [1] y + [0]
                    >= [1] y + [0]
                    =  c_2(y)     
        
* Step 7: 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))