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


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


WORST_CASE(?,O(n^3))
* Step 1: DecomposeCP.  WORST_CASE(?,O(n^3))
    + Considered Problem:
        - Strict TRS:
            a(a(x1)) -> b(c(x1))
            b(b(x1)) -> c(d(x1))
            c(c(x1)) -> d(d(d(x1)))
            d(c(x1)) -> b(f(x1))
            d(d(d(x1))) -> a(c(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeComp, withCP_ = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}}
    + Details:
        We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly:
          
          c(c(x1)) -> d(d(d(x1)))
        The Processor induces the complexity certificate TIME (?,O(n^1))
        BEST_CASE TIME (?,?)
        SPACE(?,?)
        
        Observe that weak rules from Problem (R) are non-size-increasing. Once the complexity of (R) has been
        assessed, it suffices to consider only rules whose complexity has not been estimated in (R) resulting in the
        following Problem (S). Overall the certificate is obtained by composition.
        Problem (S)
          - Strict TRS:
              a(a(x1)) -> b(c(x1))
              b(b(x1)) -> c(d(x1))
              d(c(x1)) -> b(f(x1))
              d(d(d(x1))) -> a(c(x1))
              f(f(x1)) -> f(b(x1))
          - Signature:
              {a/1,b/1,c/1,d/1,f/1} / {}
          - Obligation:
              innermost derivational complexity wrt. signature {a,b,c,d,f}
** Step 1.a:1: NaturalMI.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            a(a(x1)) -> b(c(x1))
            b(b(x1)) -> c(d(x1))
            c(c(x1)) -> d(d(d(x1)))
            d(c(x1)) -> b(f(x1))
            d(d(d(x1))) -> a(c(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on 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(a) = [1] x1 + [10]
          p(b) = [1] x1 + [9] 
          p(c) = [1] x1 + [11]
          p(d) = [1] x1 + [7] 
          p(f) = [1] x1 + [9] 
        
        Following rules are strictly oriented:
        c(c(x1)) = [1] x1 + [22]
                 > [1] x1 + [21]
                 = d(d(d(x1)))  
        
        
        Following rules are (at-least) weakly oriented:
           a(a(x1)) =  [1] x1 + [20]
                    >= [1] x1 + [20]
                    =  b(c(x1))     
        
           b(b(x1)) =  [1] x1 + [18]
                    >= [1] x1 + [18]
                    =  c(d(x1))     
        
           d(c(x1)) =  [1] x1 + [18]
                    >= [1] x1 + [18]
                    =  b(f(x1))     
        
        d(d(d(x1))) =  [1] x1 + [21]
                    >= [1] x1 + [21]
                    =  a(c(x1))     
        
           f(f(x1)) =  [1] x1 + [18]
                    >= [1] x1 + [18]
                    =  f(b(x1))     
        
** Step 1.a:2: Assumption.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict TRS:
            a(a(x1)) -> b(c(x1))
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            d(d(d(x1))) -> a(c(x1))
            f(f(x1)) -> f(b(x1))
        - Weak TRS:
            c(c(x1)) -> d(d(d(x1)))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}}
    + Details:
        ()

** Step 1.b:1: DecomposeCP.  WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            a(a(x1)) -> b(c(x1))
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            d(d(d(x1))) -> a(c(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeMul, withCP_ = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}}
    + Details:
        We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly:
          
          a(a(x1)) -> b(c(x1))
          d(d(d(x1))) -> a(c(x1))
        The Processor induces the complexity certificate TIME (?,O(n^1))
        BEST_CASE TIME (?,?)
        SPACE(?,?)
        
        Observe that Problem (R) is non-size-increasing. Once the complexity of (R) has been assessed, it suffices
        to consider only rules whose complexity has not been estimated in (R) resulting in the following Problem
        (S). Overall the certificate is obtained by multiplication.
        Problem (S)
          - Strict TRS:
              b(b(x1)) -> c(d(x1))
              d(c(x1)) -> b(f(x1))
              f(f(x1)) -> f(b(x1))
          - Signature:
              {a/1,b/1,c/1,d/1,f/1} / {}
          - Obligation:
              innermost derivational complexity wrt. signature {a,b,c,d,f}
*** Step 1.b:1.a:1: NaturalMI.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            a(a(x1)) -> b(c(x1))
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            d(d(d(x1))) -> a(c(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on 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(a) = [1] x1 + [14]
          p(b) = [1] x1 + [8] 
          p(c) = [1] x1 + [7] 
          p(d) = [1] x1 + [9] 
          p(f) = [1] x1 + [8] 
        
        Following rules are strictly oriented:
           a(a(x1)) = [1] x1 + [28]
                    > [1] x1 + [15]
                    = b(c(x1))     
        
        d(d(d(x1))) = [1] x1 + [27]
                    > [1] x1 + [21]
                    = a(c(x1))     
        
        
        Following rules are (at-least) weakly oriented:
        b(b(x1)) =  [1] x1 + [16]
                 >= [1] x1 + [16]
                 =  c(d(x1))     
        
        d(c(x1)) =  [1] x1 + [16]
                 >= [1] x1 + [16]
                 =  b(f(x1))     
        
        f(f(x1)) =  [1] x1 + [16]
                 >= [1] x1 + [16]
                 =  f(b(x1))     
        
*** Step 1.b:1.a:2: Assumption.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Strict TRS:
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            f(f(x1)) -> f(b(x1))
        - Weak TRS:
            a(a(x1)) -> b(c(x1))
            d(d(d(x1))) -> a(c(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}}
    + Details:
        ()

*** Step 1.b:1.b:1: NaturalMI.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        NaturalMI {miDimension = 2, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind triangular matrix interpretation (containing no more than 1 non-zero interpretation-entries in the diagonal of the component-wise maxima):
        
        Following symbols are considered usable:
          all
        TcT has computed the following interpretation:
          p(a) = [1 0] x1 + [0]
                 [0 0]      [0]
          p(b) = [1 0] x1 + [4]
                 [0 0]      [0]
          p(c) = [1 1] x1 + [2]
                 [0 0]      [0]
          p(d) = [1 0] x1 + [4]
                 [0 0]      [0]
          p(f) = [1 1] x1 + [2]
                 [0 0]      [2]
        
        Following rules are strictly oriented:
        b(b(x1)) = [1 0] x1 + [8]
                   [0 0]      [0]
                 > [1 0] x1 + [6]
                   [0 0]      [0]
                 = c(d(x1))      
        
        
        Following rules are (at-least) weakly oriented:
        d(c(x1)) =  [1 1] x1 + [6]
                    [0 0]      [0]
                 >= [1 1] x1 + [6]
                    [0 0]      [0]
                 =  b(f(x1))      
        
        f(f(x1)) =  [1 1] x1 + [6]
                    [0 0]      [2]
                 >= [1 0] x1 + [6]
                    [0 0]      [2]
                 =  f(b(x1))      
        
*** Step 1.b:1.b:2: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            d(c(x1)) -> b(f(x1))
            f(f(x1)) -> f(b(x1))
        - Weak TRS:
            b(b(x1)) -> c(d(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + 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 + [0]
            p(c) = [1] x1 + [0]
            p(d) = [1] x1 + [0]
            p(f) = [1] x1 + [8]
          
          Following rules are strictly oriented:
          f(f(x1)) = [1] x1 + [16]
                   > [1] x1 + [8] 
                   = f(b(x1))     
          
          
          Following rules are (at-least) weakly oriented:
          b(b(x1)) =  [1] x1 + [0]
                   >= [1] x1 + [0]
                   =  c(d(x1))    
          
          d(c(x1)) =  [1] x1 + [0]
                   >= [1] x1 + [8]
                   =  b(f(x1))    
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
*** Step 1.b:1.b:3: NaturalMI.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            d(c(x1)) -> b(f(x1))
        - Weak TRS:
            b(b(x1)) -> c(d(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        NaturalMI {miDimension = 2, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules}
    + Details:
        We apply a matrix interpretation of kind triangular matrix interpretation (containing no more than 1 non-zero interpretation-entries in the diagonal of the component-wise maxima):
        
        Following symbols are considered usable:
          all
        TcT has computed the following interpretation:
          p(a) = [1 0] x1 + [1]
                 [0 0]      [0]
          p(b) = [1 1] x1 + [4]
                 [0 0]      [0]
          p(c) = [1 6] x1 + [4]
                 [0 0]      [0]
          p(d) = [1 0] x1 + [4]
                 [0 0]      [0]
          p(f) = [1 4] x1 + [0]
                 [0 0]      [1]
        
        Following rules are strictly oriented:
        d(c(x1)) = [1 6] x1 + [8]
                   [0 0]      [0]
                 > [1 4] x1 + [5]
                   [0 0]      [0]
                 = b(f(x1))      
        
        
        Following rules are (at-least) weakly oriented:
        b(b(x1)) =  [1 1] x1 + [8]
                    [0 0]      [0]
                 >= [1 0] x1 + [8]
                    [0 0]      [0]
                 =  c(d(x1))      
        
        f(f(x1)) =  [1 4] x1 + [4]
                    [0 0]      [1]
                 >= [1 1] x1 + [4]
                    [0 0]      [1]
                 =  f(b(x1))      
        
*** Step 1.b:1.b:4: EmptyProcessor.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            b(b(x1)) -> c(d(x1))
            d(c(x1)) -> b(f(x1))
            f(f(x1)) -> f(b(x1))
        - Signature:
            {a/1,b/1,c/1,d/1,f/1} / {}
        - Obligation:
            innermost derivational complexity wrt. signature {a,b,c,d,f}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^3))