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


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


WORST_CASE(?,O(n^1))
* Step 1: WeightGap.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            a(x,g()) -> a(f(),a(g(),a(f(),x)))
            a(f(),a(f(),x)) -> a(x,g())
        - Signature:
            {a/2} / {f/0,g/0}
        - Obligation:
             derivational complexity wrt. signature {a,f,g}
    + 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 + [1] x2 + [8]
            p(f) = [0]                  
            p(g) = [0]                  
          
          Following rules are strictly oriented:
          a(f(),a(f(),x)) = [1] x + [16]
                          > [1] x + [8] 
                          = a(x,g())    
          
          
          Following rules are (at-least) weakly oriented:
          a(x,g()) =  [1] x + [8]           
                   >= [1] x + [24]          
                   =  a(f(),a(g(),a(f(),x)))
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 2: Bounds.  WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            a(x,g()) -> a(f(),a(g(),a(f(),x)))
        - Weak TRS:
            a(f(),a(f(),x)) -> a(x,g())
        - Signature:
            {a/2} / {f/0,g/0}
        - Obligation:
             derivational complexity wrt. signature {a,f,g}
    + Applied Processor:
        Bounds {initialAutomaton = minimal, enrichment = match}
    + Details:
        The problem is match-bounded by 3.
        The enriched problem is compatible with follwoing automaton.
          a_0(1,1) -> 1
          a_1(1,4) -> 5
          a_1(1,4) -> 11
          a_1(2,3) -> 1
          a_1(3,4) -> 1
          a_1(3,4) -> 5
          a_1(4,5) -> 3
          a_1(4,7) -> 1
          a_1(4,16) -> 15
          a_1(6,1) -> 5
          a_1(6,6) -> 7
          a_1(6,12) -> 16
          a_1(6,15) -> 11
          a_1(13,4) -> 1
          a_2(3,10) -> 11
          a_2(8,9) -> 5
          a_2(10,5) -> 13
          a_2(10,11) -> 9
          a_2(10,14) -> 13
          a_2(12,1) -> 11
          a_2(12,3) -> 14
          a_2(12,9) -> 11
          a_2(12,13) -> 1
          a_2(12,13) -> 5
          a_2(13,10) -> 5
          a_2(13,10) -> 11
          a_3(17,18) -> 11
          a_3(19,20) -> 18
          a_3(19,23) -> 22
          a_3(21,3) -> 20
          a_3(21,13) -> 23
          a_3(21,22) -> 5
          a_3(21,22) -> 11
          f_0() -> 1
          f_1() -> 2
          f_1() -> 6
          f_2() -> 8
          f_2() -> 12
          f_3() -> 17
          f_3() -> 21
          g_0() -> 1
          g_1() -> 4
          g_2() -> 10
          g_3() -> 19
* Step 3: EmptyProcessor.  WORST_CASE(?,O(1))
    + Considered Problem:
        - Weak TRS:
            a(x,g()) -> a(f(),a(g(),a(f(),x)))
            a(f(),a(f(),x)) -> a(x,g())
        - Signature:
            {a/2} / {f/0,g/0}
        - Obligation:
             derivational complexity wrt. signature {a,f,g}
    + Applied Processor:
        EmptyProcessor
    + Details:
        The problem is already closed. The intended complexity is O(1).

WORST_CASE(?,O(n^1))