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


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


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).

(0) CpxTRS
(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
    (4) CpxTRS
    (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
    (6) CpxRelTRS
    (7) RcToIrcProof [BOTH BOUNDS(ID, ID), 4 ms]
    (8) CpxRelTRS
    (9) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
    (10) CdtProblem
    (11) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CdtProblem
    (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 87 ms]
    (16) CdtProblem
    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 2 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 145 ms]
    (20) CdtProblem
    (21) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (22) BOUNDS(1, 1)
(23) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(24) TRS for Loop Detection
    (25) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (26) BEST
        (27) proven lower bound
            (28) LowerBoundPropagationProof [FINISHED, 0 ms]
            (29) BOUNDS(n^1, INF)
        (30) TRS for Loop Detection


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

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   +(s(x), s(y)) -> s(s(+(x, y)))
   +(+(x, y), z) -> +(x, +(y, z))
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) DependencyGraphProof (UPPER BOUND(ID))
The following rules are not reachable from basic terms in the dependency graph and can be removed:

+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))

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

(2)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
The following defined symbols can occur below the 0th argument of sum: s, a
The following defined symbols can occur below the 0th argument of a: s, a
The following defined symbols can occur below the 1th argument of a: s, a

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))

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

(4)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(5) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

(6)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
   a(c_s(l), h, h, z) -> a(l, z, h, z)
   a(l, c_s(x), h, z) -> a(l, x, z, z)

The (relative) TRS S consists of the following rules:

   s(x0) -> c_s(x0)

Rewrite Strategy: FULL
----------------------------------------

(7) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

The duplicating contexts are:
a(c_s(l), h, h, [])
a(l, c_s(x), h, [])


The defined contexts are:
sum(cons([], x1))
a([], x1, h, h)
a([], x1, h, x2)
a([], x1, x2, x3)


[] just represents basic- or constructor-terms in the following defined contexts:
sum(cons([], x1))


As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
----------------------------------------

(8)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
   a(c_s(l), h, h, z) -> a(l, z, h, z)
   a(l, c_s(x), h, z) -> a(l, x, z, z)

The (relative) TRS S consists of the following rules:

   s(x0) -> c_s(x0)

Rewrite Strategy: INNERMOST
----------------------------------------

(9) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   s(z0) -> c_s(z0)
   s(h) -> 1
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   +(z0, h) -> z0
   +(h, z0) -> z0
   app(nil, z0) -> z0
   app(z0, nil) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   sum(cons(z0, nil)) -> cons(z0, nil)
   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))
Tuples:
   S(z0) -> c
   S(h) -> c1
   A(h, h, h, z0) -> c2(S(z0))
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   +'(z0, h) -> c5
   +'(h, z0) -> c6
   APP(nil, z0) -> c7
   APP(z0, nil) -> c8
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, nil)) -> c10
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:
   S(h) -> c1
   A(h, h, h, z0) -> c2(S(z0))
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   +'(z0, h) -> c5
   +'(h, z0) -> c6
   APP(nil, z0) -> c7
   APP(z0, nil) -> c8
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, nil)) -> c10
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
K tuples:none
Defined Rule Symbols:   a_4, +_2, s_1, app_2, sum_1

Defined Pair Symbols:   S_1, A_4, +'_2, APP_2, SUM_1

Compound Symbols:   c, c1, c2_1, c3_1, c4_1, c5, c6, c7, c8, c9_1, c10, c11_2


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

(11) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 8 trailing nodes:
   A(h, h, h, z0) -> c2(S(z0))
   SUM(cons(z0, nil)) -> c10
   APP(z0, nil) -> c8
   S(z0) -> c
   S(h) -> c1
   +'(h, z0) -> c6
   APP(nil, z0) -> c7
   +'(z0, h) -> c5

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   s(z0) -> c_s(z0)
   s(h) -> 1
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   +(z0, h) -> z0
   +(h, z0) -> z0
   app(nil, z0) -> z0
   app(z0, nil) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   sum(cons(z0, nil)) -> cons(z0, nil)
   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))
Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
K tuples:none
Defined Rule Symbols:   a_4, +_2, s_1, app_2, sum_1

Defined Pair Symbols:   A_4, APP_2, SUM_1

Compound Symbols:   c3_1, c4_1, c9_1, c11_2


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

(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   +(z0, h) -> z0
   +(h, z0) -> z0
   app(nil, z0) -> z0
   app(z0, nil) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   sum(cons(z0, nil)) -> cons(z0, nil)
   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   s(z0) -> c_s(z0)
   s(h) -> 1
Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
K tuples:none
Defined Rule Symbols:   a_4, s_1

Defined Pair Symbols:   A_4, APP_2, SUM_1

Compound Symbols:   c3_1, c4_1, c9_1, c11_2


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

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
We considered the (Usable) Rules:
   s(z0) -> c_s(z0)
   a(h, h, h, z0) -> s(z0)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   s(h) -> 1
And the Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(1) = 0
   POL(A(x_1, x_2, x_3, x_4)) = 0
   POL(APP(x_1, x_2)) = x_1
   POL(SUM(x_1)) = x_1
   POL(a(x_1, x_2, x_3, x_4)) = 0
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c9(x_1)) = x_1
   POL(c_s(x_1)) = 0
   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(h) = [1]
   POL(s(x_1)) = 0

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   s(z0) -> c_s(z0)
   s(h) -> 1
Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
K tuples:
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
Defined Rule Symbols:   a_4, s_1

Defined Pair Symbols:   A_4, APP_2, SUM_1

Compound Symbols:   c3_1, c4_1, c9_1, c11_2


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

(17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
We considered the (Usable) Rules:
   s(z0) -> c_s(z0)
   a(h, h, h, z0) -> s(z0)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   s(h) -> 1
And the Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(1) = [1]
   POL(A(x_1, x_2, x_3, x_4)) = x_1 + x_4
   POL(APP(x_1, x_2)) = x_1
   POL(SUM(x_1)) = x_1
   POL(a(x_1, x_2, x_3, x_4)) = [1] + x_4
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c9(x_1)) = x_1
   POL(c_s(x_1)) = [1] + x_1
   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(h) = 0
   POL(s(x_1)) = [1] + x_1

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

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   s(z0) -> c_s(z0)
   s(h) -> 1
Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
K tuples:
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
Defined Rule Symbols:   a_4, s_1

Defined Pair Symbols:   A_4, APP_2, SUM_1

Compound Symbols:   c3_1, c4_1, c9_1, c11_2


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

(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
We considered the (Usable) Rules:
   s(z0) -> c_s(z0)
   a(h, h, h, z0) -> s(z0)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   s(h) -> 1
And the Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(1) = [2]
   POL(A(x_1, x_2, x_3, x_4)) = x_2 + [2]x_4 + [2]x_4^2 + x_1*x_4
   POL(APP(x_1, x_2)) = [2]x_1 + [2]x_1*x_2 + x_1^2
   POL(SUM(x_1)) = x_1^2
   POL(a(x_1, x_2, x_3, x_4)) = [2] + x_4
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c9(x_1)) = x_1
   POL(c_s(x_1)) = [1] + x_1
   POL(cons(x_1, x_2)) = [2] + x_1 + x_2
   POL(h) = 0
   POL(s(x_1)) = [2] + x_1

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

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   a(h, h, h, z0) -> s(z0)
   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
   s(z0) -> c_s(z0)
   s(h) -> 1
Tuples:
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
S tuples:none
K tuples:
   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
Defined Rule Symbols:   a_4, s_1

Defined Pair Symbols:   A_4, APP_2, SUM_1

Compound Symbols:   c3_1, c4_1, c9_1, c11_2


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

(21) SIsEmptyProof (BOTH BOUNDS(ID, ID))
The set S is empty
----------------------------------------

(22)
BOUNDS(1, 1)

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

(23) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(24)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   +(s(x), s(y)) -> s(s(+(x, y)))
   +(+(x, y), z) -> +(x, +(y, z))
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(25) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

app(cons(x, l), k) ->^+ cons(x, app(l, k))

gives rise to a decreasing loop by considering the right hand sides subterm at position [1].

The pumping substitution is [l / cons(x, l)].

The result substitution is [ ].




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

(26)
Complex Obligation (BEST)

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

(27)
Obligation:
Proved the lower bound n^1 for the following obligation:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   +(s(x), s(y)) -> s(s(+(x, y)))
   +(+(x, y), z) -> +(x, +(y, z))
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(28) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(29)
BOUNDS(n^1, INF)

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

(30)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   +(s(x), s(y)) -> s(s(+(x, y)))
   +(+(x, y), z) -> +(x, +(y, z))
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

S is empty.
Rewrite Strategy: FULL