343.01/291.57	WORST_CASE(Omega(n^1), O(n^2))
343.11/291.59	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
343.11/291.59	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
343.11/291.59	
343.11/291.59	
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
343.11/291.59	
343.11/291.59	(0) CpxTRS
343.11/291.59	(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
343.11/291.59	(2) CpxTRS
343.11/291.59	    (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 11 ms]
343.11/291.59	    (4) CpxTRS
343.11/291.59	    (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
343.11/291.59	    (6) CpxRelTRS
343.11/291.59	    (7) RcToIrcProof [BOTH BOUNDS(ID, ID), 8 ms]
343.11/291.59	    (8) CpxRelTRS
343.11/291.59	    (9) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
343.11/291.59	    (10) CdtProblem
343.11/291.59	    (11) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
343.11/291.59	    (12) CdtProblem
343.11/291.59	    (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
343.11/291.59	    (14) CdtProblem
343.11/291.59	    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 201 ms]
343.11/291.59	    (16) CdtProblem
343.11/291.59	    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 15 ms]
343.11/291.59	    (18) CdtProblem
343.11/291.59	    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 11 ms]
343.11/291.59	    (20) CdtProblem
343.11/291.59	    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 69 ms]
343.11/291.59	    (22) CdtProblem
343.11/291.59	    (23) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
343.11/291.59	    (24) BOUNDS(1, 1)
343.11/291.59	(25) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
343.11/291.59	(26) TRS for Loop Detection
343.11/291.59	    (27) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
343.11/291.59	    (28) BEST
343.11/291.59	        (29) proven lower bound
343.11/291.59	            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
343.11/291.59	            (31) BOUNDS(n^1, INF)
343.11/291.59	        (32) TRS for Loop Detection
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(0)
343.11/291.59	Obligation:
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   +(s(x), s(y)) -> s(s(+(x, y)))
343.11/291.59	   +(+(x, y), z) -> +(x, +(y, z))
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(1) DependencyGraphProof (UPPER BOUND(ID))
343.11/291.59	The following rules are not reachable from basic terms in the dependency graph and can be removed:
343.11/291.59	
343.11/291.59	+(s(x), s(y)) -> s(s(+(x, y)))
343.11/291.59	+(+(x, y), z) -> +(x, +(y, z))
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(2)
343.11/291.59	Obligation:
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
343.11/291.59	The following defined symbols can occur below the 0th argument of sum: s, a
343.11/291.59	The following defined symbols can occur below the 0th argument of a: s, a
343.11/291.59	The following defined symbols can occur below the 1th argument of a: s, a
343.11/291.59	
343.11/291.59	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
343.11/291.59	a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(4)
343.11/291.59	Obligation:
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(5) NonCtorToCtorProof (UPPER BOUND(ID))
343.11/291.59	transformed non-ctor to ctor-system
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(6)
343.11/291.59	Obligation:
343.11/291.59	The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	   a(c_s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   a(l, c_s(x), h, z) -> a(l, x, z, z)
343.11/291.59	
343.11/291.59	The (relative) TRS S consists of the following rules:
343.11/291.59	
343.11/291.59	   s(x0) -> c_s(x0)
343.11/291.59	
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(7) RcToIrcProof (BOTH BOUNDS(ID, ID))
343.11/291.59	Converted rc-obligation to irc-obligation.
343.11/291.59	
343.11/291.59	The duplicating contexts are:
343.11/291.59	a(c_s(l), h, h, [])
343.11/291.59	a(l, c_s(x), h, [])
343.11/291.59	
343.11/291.59	
343.11/291.59	The defined contexts are:
343.11/291.59	sum(cons([], x1))
343.11/291.59	a([], x1, h, h)
343.11/291.59	a([], x1, h, x2)
343.11/291.59	a([], x1, x2, x3)
343.11/291.59	
343.11/291.59	
343.11/291.59	[] just represents basic- or constructor-terms in the following defined contexts:
343.11/291.59	sum(cons([], x1))
343.11/291.59	
343.11/291.59	
343.11/291.59	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(8)
343.11/291.59	Obligation:
343.11/291.59	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	   a(c_s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   a(l, c_s(x), h, z) -> a(l, x, z, z)
343.11/291.59	
343.11/291.59	The (relative) TRS S consists of the following rules:
343.11/291.59	
343.11/291.59	   s(x0) -> c_s(x0)
343.11/291.59	
343.11/291.59	Rewrite Strategy: INNERMOST
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(9) CpxTrsToCdtProof (UPPER BOUND(ID))
343.11/291.59	Converted Cpx (relative) TRS to CDT
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(10)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   +(z0, h) -> z0
343.11/291.59	   +(h, z0) -> z0
343.11/291.59	   app(nil, z0) -> z0
343.11/291.59	   app(z0, nil) -> z0
343.11/291.59	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
343.11/291.59	   sum(cons(z0, nil)) -> cons(z0, nil)
343.11/291.59	   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))
343.11/291.59	Tuples:
343.11/291.59	   S(z0) -> c
343.11/291.59	   S(h) -> c1
343.11/291.59	   A(h, h, h, z0) -> c2(S(z0))
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   +'(z0, h) -> c5
343.11/291.59	   +'(h, z0) -> c6
343.11/291.59	   APP(nil, z0) -> c7
343.11/291.59	   APP(z0, nil) -> c8
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, nil)) -> c10
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   S(h) -> c1
343.11/291.59	   A(h, h, h, z0) -> c2(S(z0))
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   +'(z0, h) -> c5
343.11/291.59	   +'(h, z0) -> c6
343.11/291.59	   APP(nil, z0) -> c7
343.11/291.59	   APP(z0, nil) -> c8
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, nil)) -> c10
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	K tuples:none
343.11/291.59	Defined Rule Symbols:   a_4, +_2, s_1, app_2, sum_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   S_1, A_4, +'_2, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c, c1, c2_1, c3_1, c4_1, c5, c6, c7, c8, c9_1, c10, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(11) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
343.11/291.59	Removed 8 trailing nodes:
343.11/291.59	   APP(nil, z0) -> c7
343.11/291.59	   +'(h, z0) -> c6
343.11/291.59	   S(z0) -> c
343.11/291.59	   APP(z0, nil) -> c8
343.11/291.59	   A(h, h, h, z0) -> c2(S(z0))
343.11/291.59	   +'(z0, h) -> c5
343.11/291.59	   SUM(cons(z0, nil)) -> c10
343.11/291.59	   S(h) -> c1
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(12)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   +(z0, h) -> z0
343.11/291.59	   +(h, z0) -> z0
343.11/291.59	   app(nil, z0) -> z0
343.11/291.59	   app(z0, nil) -> z0
343.11/291.59	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
343.11/291.59	   sum(cons(z0, nil)) -> cons(z0, nil)
343.11/291.59	   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	K tuples:none
343.11/291.59	Defined Rule Symbols:   a_4, +_2, s_1, app_2, sum_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
343.11/291.59	The following rules are not usable and were removed:
343.11/291.59	   +(z0, h) -> z0
343.11/291.59	   +(h, z0) -> z0
343.11/291.59	   app(nil, z0) -> z0
343.11/291.59	   app(z0, nil) -> z0
343.11/291.59	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
343.11/291.59	   sum(cons(z0, nil)) -> cons(z0, nil)
343.11/291.59	   sum(cons(z0, cons(z1, z2))) -> sum(cons(a(z0, z1, h, h), z2))
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(14)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	K tuples:none
343.11/291.59	Defined Rule Symbols:   a_4, s_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
343.11/291.59	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	We considered the (Usable) Rules:none
343.11/291.59	And the Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	The order we found is given by the following interpretation:
343.11/291.59	
343.11/291.59	Polynomial interpretation :
343.11/291.59	
343.11/291.59	   POL(1) = [1]
343.11/291.59	   POL(A(x_1, x_2, x_3, x_4)) = [1] + [2]x_4 + x_4^2
343.11/291.59	   POL(APP(x_1, x_2)) = x_1*x_2
343.11/291.59	   POL(SUM(x_1)) = [2]x_1 + x_1^2
343.11/291.59	   POL(a(x_1, x_2, x_3, x_4)) = 0
343.11/291.59	   POL(c11(x_1, x_2)) = x_1 + x_2
343.11/291.59	   POL(c3(x_1)) = x_1
343.11/291.59	   POL(c4(x_1)) = x_1
343.11/291.59	   POL(c9(x_1)) = x_1
343.11/291.59	   POL(c_s(x_1)) = x_1
343.11/291.59	   POL(cons(x_1, x_2)) = [1] + x_2
343.11/291.59	   POL(h) = 0
343.11/291.59	   POL(s(x_1)) = [1] + x_1 + x_1^2
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(16)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	K tuples:
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	Defined Rule Symbols:   a_4, s_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
343.11/291.59	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	We considered the (Usable) Rules:
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   s(h) -> 1
343.11/291.59	And the Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	The order we found is given by the following interpretation:
343.11/291.59	
343.11/291.59	Polynomial interpretation :
343.11/291.59	
343.11/291.59	   POL(1) = 0
343.11/291.59	   POL(A(x_1, x_2, x_3, x_4)) = 0
343.11/291.59	   POL(APP(x_1, x_2)) = x_1
343.11/291.59	   POL(SUM(x_1)) = x_1
343.11/291.59	   POL(a(x_1, x_2, x_3, x_4)) = x_1 + x_4
343.11/291.59	   POL(c11(x_1, x_2)) = x_1 + x_2
343.11/291.59	   POL(c3(x_1)) = x_1
343.11/291.59	   POL(c4(x_1)) = x_1
343.11/291.59	   POL(c9(x_1)) = x_1
343.11/291.59	   POL(c_s(x_1)) = [1] + x_1
343.11/291.59	   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
343.11/291.59	   POL(h) = [1]
343.11/291.59	   POL(s(x_1)) = [1] + x_1
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(18)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	K tuples:
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	Defined Rule Symbols:   a_4, s_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
343.11/291.59	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	We considered the (Usable) Rules:
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   s(h) -> 1
343.11/291.59	And the Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	The order we found is given by the following interpretation:
343.11/291.59	
343.11/291.59	Polynomial interpretation :
343.11/291.59	
343.11/291.59	   POL(1) = [1]
343.11/291.59	   POL(A(x_1, x_2, x_3, x_4)) = x_1 + x_4
343.11/291.59	   POL(APP(x_1, x_2)) = x_1
343.11/291.59	   POL(SUM(x_1)) = x_1
343.11/291.59	   POL(a(x_1, x_2, x_3, x_4)) = [1] + x_4
343.11/291.59	   POL(c11(x_1, x_2)) = x_1 + x_2
343.11/291.59	   POL(c3(x_1)) = x_1
343.11/291.59	   POL(c4(x_1)) = x_1
343.11/291.59	   POL(c9(x_1)) = x_1
343.11/291.59	   POL(c_s(x_1)) = [1] + x_1
343.11/291.59	   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
343.11/291.59	   POL(h) = 0
343.11/291.59	   POL(s(x_1)) = [1] + x_1
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(20)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	K tuples:
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	Defined Rule Symbols:   a_4, s_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
343.11/291.59	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	We considered the (Usable) Rules:
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   s(h) -> 1
343.11/291.59	And the Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	The order we found is given by the following interpretation:
343.11/291.59	
343.11/291.59	Polynomial interpretation :
343.11/291.59	
343.11/291.59	   POL(1) = [2]
343.11/291.59	   POL(A(x_1, x_2, x_3, x_4)) = x_2 + [2]x_4 + [2]x_4^2 + x_1*x_4
343.11/291.59	   POL(APP(x_1, x_2)) = [2]x_1 + [2]x_1*x_2 + x_1^2
343.11/291.59	   POL(SUM(x_1)) = x_1^2
343.11/291.59	   POL(a(x_1, x_2, x_3, x_4)) = [2] + x_4
343.11/291.59	   POL(c11(x_1, x_2)) = x_1 + x_2
343.11/291.59	   POL(c3(x_1)) = x_1
343.11/291.59	   POL(c4(x_1)) = x_1
343.11/291.59	   POL(c9(x_1)) = x_1
343.11/291.59	   POL(c_s(x_1)) = [1] + x_1
343.11/291.59	   POL(cons(x_1, x_2)) = [2] + x_1 + x_2
343.11/291.59	   POL(h) = 0
343.11/291.59	   POL(s(x_1)) = [2] + x_1
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(22)
343.11/291.59	Obligation:
343.11/291.59	Complexity Dependency Tuples Problem
343.11/291.59	
343.11/291.59	Rules:
343.11/291.59	   a(h, h, h, z0) -> s(z0)
343.11/291.59	   a(c_s(z0), h, h, z1) -> a(z0, z1, h, z1)
343.11/291.59	   a(z0, c_s(z1), h, z2) -> a(z0, z1, z2, z2)
343.11/291.59	   s(z0) -> c_s(z0)
343.11/291.59	   s(h) -> 1
343.11/291.59	Tuples:
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	S tuples:none
343.11/291.59	K tuples:
343.11/291.59	   SUM(cons(z0, cons(z1, z2))) -> c11(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
343.11/291.59	   APP(cons(z0, z1), z2) -> c9(APP(z1, z2))
343.11/291.59	   A(c_s(z0), h, h, z1) -> c3(A(z0, z1, h, z1))
343.11/291.59	   A(z0, c_s(z1), h, z2) -> c4(A(z0, z1, z2, z2))
343.11/291.59	Defined Rule Symbols:   a_4, s_1
343.11/291.59	
343.11/291.59	Defined Pair Symbols:   A_4, APP_2, SUM_1
343.11/291.59	
343.11/291.59	Compound Symbols:   c3_1, c4_1, c9_1, c11_2
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(23) SIsEmptyProof (BOTH BOUNDS(ID, ID))
343.11/291.59	The set S is empty
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(24)
343.11/291.59	BOUNDS(1, 1)
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(25) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
343.11/291.59	Transformed a relative TRS into a decreasing-loop problem.
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(26)
343.11/291.59	Obligation:
343.11/291.59	Analyzing the following TRS for decreasing loops:
343.11/291.59	
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   +(s(x), s(y)) -> s(s(+(x, y)))
343.11/291.59	   +(+(x, y), z) -> +(x, +(y, z))
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(27) DecreasingLoopProof (LOWER BOUND(ID))
343.11/291.59	The following loop(s) give(s) rise to the lower bound Omega(n^1):
343.11/291.59	
343.11/291.59	The rewrite sequence
343.11/291.59	
343.11/291.59	app(cons(x, l), k) ->^+ cons(x, app(l, k))
343.11/291.59	
343.11/291.59	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
343.11/291.59	
343.11/291.59	The pumping substitution is [l / cons(x, l)].
343.11/291.59	
343.11/291.59	The result substitution is [ ].
343.11/291.59	
343.11/291.59	
343.11/291.59	
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(28)
343.11/291.59	Complex Obligation (BEST)
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(29)
343.11/291.59	Obligation:
343.11/291.59	Proved the lower bound n^1 for the following obligation:
343.11/291.59	
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   +(s(x), s(y)) -> s(s(+(x, y)))
343.11/291.59	   +(+(x, y), z) -> +(x, +(y, z))
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(30) LowerBoundPropagationProof (FINISHED)
343.11/291.59	Propagated lower bound.
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(31)
343.11/291.59	BOUNDS(n^1, INF)
343.11/291.59	
343.11/291.59	----------------------------------------
343.11/291.59	
343.11/291.59	(32)
343.11/291.59	Obligation:
343.11/291.59	Analyzing the following TRS for decreasing loops:
343.11/291.59	
343.11/291.59	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
343.11/291.59	
343.11/291.59	
343.11/291.59	The TRS R consists of the following rules:
343.11/291.59	
343.11/291.59	   a(h, h, h, x) -> s(x)
343.11/291.59	   a(l, x, s(y), h) -> a(l, x, y, s(h))
343.11/291.59	   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
343.11/291.59	   a(l, s(x), h, z) -> a(l, x, z, z)
343.11/291.59	   a(s(l), h, h, z) -> a(l, z, h, z)
343.11/291.59	   +(x, h) -> x
343.11/291.59	   +(h, x) -> x
343.11/291.59	   +(s(x), s(y)) -> s(s(+(x, y)))
343.11/291.59	   +(+(x, y), z) -> +(x, +(y, z))
343.11/291.59	   s(h) -> 1
343.11/291.59	   app(nil, k) -> k
343.11/291.59	   app(l, nil) -> l
343.11/291.59	   app(cons(x, l), k) -> cons(x, app(l, k))
343.11/291.59	   sum(cons(x, nil)) -> cons(x, nil)
343.11/291.59	   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
343.11/291.59	
343.11/291.59	S is empty.
343.11/291.59	Rewrite Strategy: FULL
343.19/291.64	EOF