/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^2))
* Step 1: DecomposeCP.  WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            f(a(),f(f(a(),x),a())) -> f(f(a(),f(a(),x)),a())
        - Signature:
            {f/2} / {a/0}
        - Obligation:
            innermost derivational complexity wrt. signature {a,f}
    + Applied Processor:
        DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeMul, withCP_ = NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}}
    + Details:
        We first use the processor NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly:
          
          f(a(),f(f(a(),x),a())) -> f(f(a(),f(a(),x)),a())
        The Processor induces the complexity certificate TIME (?,O(n^2))
        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)
          
          - Signature:
              {f/2} / {a/0}
          - Obligation:
              innermost derivational complexity wrt. signature {a,f}
** Step 1.a:1: NaturalMI.  WORST_CASE(?,O(n^2))
    + Considered Problem:
        - Strict TRS:
            f(a(),f(f(a(),x),a())) -> f(f(a(),f(a(),x)),a())
        - Signature:
            {f/2} / {a/0}
        - Obligation:
            innermost derivational complexity wrt. signature {a,f}
    + Applied Processor:
        NaturalMI {miDimension = 2, miDegree = 2, 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) = [0]                      
                 [0]                      
          p(f) = [1 0] x1 + [1 1] x2 + [0]
                 [0 1]      [0 1]      [2]
        
        Following rules are strictly oriented:
        f(a(),f(f(a(),x),a())) = [1 2] x + [4]         
                                 [0 1]     [6]         
                               > [1 2] x + [2]         
                                 [0 1]     [6]         
                               = f(f(a(),f(a(),x)),a())
        
        
        Following rules are (at-least) weakly oriented:
        
** Step 1.a:2: Assumption.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            f(a(),f(f(a(),x),a())) -> f(f(a(),f(a(),x)),a())
        - Signature:
            {f/2} / {a/0}
        - Obligation:
            innermost derivational complexity wrt. signature {a,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: EmptyProcessor.  WORST_CASE(?,O(1))
    + Considered Problem:
        
        - Signature:
            {f/2} / {a/0}
        - Obligation:
            innermost derivational complexity wrt. signature {a,f}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^2))