336.88/291.52	WORST_CASE(Omega(n^1), O(n^2))
336.88/291.53	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
336.88/291.53	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
336.88/291.53	
336.88/291.53	
336.88/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
336.88/291.53	
336.88/291.53	(0) CpxTRS
336.88/291.53	(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
336.88/291.53	(2) CpxTRS
336.88/291.53	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	    (4) CpxTRS
336.88/291.53	    (5) CpxTrsToCdtProof [UPPER BOUND(ID), 3 ms]
336.88/291.53	    (6) CdtProblem
336.88/291.53	    (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	    (8) CdtProblem
336.88/291.53	    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	    (10) CdtProblem
336.88/291.53	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 47 ms]
336.88/291.53	    (12) CdtProblem
336.88/291.53	    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 27 ms]
336.88/291.53	    (14) CdtProblem
336.88/291.53	    (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	    (16) BOUNDS(1, 1)
336.88/291.53	(17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	(18) CpxTRS
336.88/291.53	    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
336.88/291.53	    (20) typed CpxTrs
336.88/291.53	    (21) OrderProof [LOWER BOUND(ID), 0 ms]
336.88/291.53	    (22) typed CpxTrs
336.88/291.53	    (23) RewriteLemmaProof [LOWER BOUND(ID), 318 ms]
336.88/291.53	    (24) BEST
336.88/291.53	        (25) proven lower bound
336.88/291.53	            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
336.88/291.53	            (27) BOUNDS(n^1, INF)
336.88/291.53	        (28) typed CpxTrs
336.88/291.53	
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(0)
336.88/291.53	Obligation:
336.88/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
336.88/291.53	
336.88/291.53	
336.88/291.53	The TRS R consists of the following rules:
336.88/291.53	
336.88/291.53	   app(nil, k) -> k
336.88/291.53	   app(l, nil) -> l
336.88/291.53	   app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.53	   sum(cons(x, nil)) -> cons(x, nil)
336.88/291.53	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.53	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.53	   plus(0, y) -> y
336.88/291.53	   plus(s(x), y) -> s(plus(x, y))
336.88/291.53	   sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.53	   pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.53	
336.88/291.53	S is empty.
336.88/291.53	Rewrite Strategy: FULL
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(1) DependencyGraphProof (UPPER BOUND(ID))
336.88/291.53	The following rules are not reachable from basic terms in the dependency graph and can be removed:
336.88/291.53	
336.88/291.53	sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.53	sum(plus(cons(0, x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(2)
336.88/291.53	Obligation:
336.88/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).
336.88/291.53	
336.88/291.53	
336.88/291.53	The TRS R consists of the following rules:
336.88/291.53	
336.88/291.53	   app(nil, k) -> k
336.88/291.53	   app(l, nil) -> l
336.88/291.53	   app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.53	   sum(cons(x, nil)) -> cons(x, nil)
336.88/291.53	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.53	   plus(0, y) -> y
336.88/291.53	   plus(s(x), y) -> s(plus(x, y))
336.88/291.53	   pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.53	
336.88/291.53	S is empty.
336.88/291.53	Rewrite Strategy: FULL
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
336.88/291.53	Converted rc-obligation to irc-obligation.
336.88/291.53	
336.88/291.53	As the TRS is a non-duplicating overlay system, we have rc = irc.
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(4)
336.88/291.53	Obligation:
336.88/291.53	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).
336.88/291.53	
336.88/291.53	
336.88/291.53	The TRS R consists of the following rules:
336.88/291.53	
336.88/291.53	   app(nil, k) -> k
336.88/291.53	   app(l, nil) -> l
336.88/291.53	   app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.53	   sum(cons(x, nil)) -> cons(x, nil)
336.88/291.53	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.53	   plus(0, y) -> y
336.88/291.53	   plus(s(x), y) -> s(plus(x, y))
336.88/291.53	   pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.53	
336.88/291.53	S is empty.
336.88/291.53	Rewrite Strategy: INNERMOST
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(5) CpxTrsToCdtProof (UPPER BOUND(ID))
336.88/291.53	Converted Cpx (relative) TRS to CDT
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(6)
336.88/291.53	Obligation:
336.88/291.53	Complexity Dependency Tuples Problem
336.88/291.53	
336.88/291.53	Rules:
336.88/291.53	   app(nil, z0) -> z0
336.88/291.53	   app(z0, nil) -> z0
336.88/291.53	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
336.88/291.53	   sum(cons(z0, nil)) -> cons(z0, nil)
336.88/291.53	   sum(cons(z0, cons(z1, z2))) -> sum(cons(plus(z0, z1), z2))
336.88/291.53	   plus(0, z0) -> z0
336.88/291.53	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.53	   pred(cons(s(z0), nil)) -> cons(z0, nil)
336.88/291.53	Tuples:
336.88/291.53	   APP(nil, z0) -> c
336.88/291.53	   APP(z0, nil) -> c1
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, nil)) -> c3
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(0, z0) -> c5
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	   PRED(cons(s(z0), nil)) -> c7
336.88/291.53	S tuples:
336.88/291.53	   APP(nil, z0) -> c
336.88/291.53	   APP(z0, nil) -> c1
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, nil)) -> c3
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(0, z0) -> c5
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	   PRED(cons(s(z0), nil)) -> c7
336.88/291.53	K tuples:none
336.88/291.53	Defined Rule Symbols:   app_2, sum_1, plus_2, pred_1
336.88/291.53	
336.88/291.53	Defined Pair Symbols:   APP_2, SUM_1, PLUS_2, PRED_1
336.88/291.53	
336.88/291.53	Compound Symbols:   c, c1, c2_1, c3, c4_2, c5, c6_1, c7
336.88/291.53	
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
336.88/291.53	Removed 5 trailing nodes:
336.88/291.53	   SUM(cons(z0, nil)) -> c3
336.88/291.53	   APP(z0, nil) -> c1
336.88/291.53	   PRED(cons(s(z0), nil)) -> c7
336.88/291.53	   PLUS(0, z0) -> c5
336.88/291.53	   APP(nil, z0) -> c
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(8)
336.88/291.53	Obligation:
336.88/291.53	Complexity Dependency Tuples Problem
336.88/291.53	
336.88/291.53	Rules:
336.88/291.53	   app(nil, z0) -> z0
336.88/291.53	   app(z0, nil) -> z0
336.88/291.53	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
336.88/291.53	   sum(cons(z0, nil)) -> cons(z0, nil)
336.88/291.53	   sum(cons(z0, cons(z1, z2))) -> sum(cons(plus(z0, z1), z2))
336.88/291.53	   plus(0, z0) -> z0
336.88/291.53	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.53	   pred(cons(s(z0), nil)) -> cons(z0, nil)
336.88/291.53	Tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	S tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	K tuples:none
336.88/291.53	Defined Rule Symbols:   app_2, sum_1, plus_2, pred_1
336.88/291.53	
336.88/291.53	Defined Pair Symbols:   APP_2, SUM_1, PLUS_2
336.88/291.53	
336.88/291.53	Compound Symbols:   c2_1, c4_2, c6_1
336.88/291.53	
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
336.88/291.53	The following rules are not usable and were removed:
336.88/291.53	   app(nil, z0) -> z0
336.88/291.53	   app(z0, nil) -> z0
336.88/291.53	   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
336.88/291.53	   sum(cons(z0, nil)) -> cons(z0, nil)
336.88/291.53	   sum(cons(z0, cons(z1, z2))) -> sum(cons(plus(z0, z1), z2))
336.88/291.53	   pred(cons(s(z0), nil)) -> cons(z0, nil)
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(10)
336.88/291.53	Obligation:
336.88/291.53	Complexity Dependency Tuples Problem
336.88/291.53	
336.88/291.53	Rules:
336.88/291.53	   plus(0, z0) -> z0
336.88/291.53	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.53	Tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	S tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	K tuples:none
336.88/291.53	Defined Rule Symbols:   plus_2
336.88/291.53	
336.88/291.53	Defined Pair Symbols:   APP_2, SUM_1, PLUS_2
336.88/291.53	
336.88/291.53	Compound Symbols:   c2_1, c4_2, c6_1
336.88/291.53	
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
336.88/291.53	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	We considered the (Usable) Rules:none
336.88/291.53	And the Tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	The order we found is given by the following interpretation:
336.88/291.53	
336.88/291.53	Polynomial interpretation :
336.88/291.53	
336.88/291.53	   POL(0) = 0
336.88/291.53	   POL(APP(x_1, x_2)) = x_1
336.88/291.53	   POL(PLUS(x_1, x_2)) = 0
336.88/291.53	   POL(SUM(x_1)) = x_1
336.88/291.53	   POL(c2(x_1)) = x_1
336.88/291.53	   POL(c4(x_1, x_2)) = x_1 + x_2
336.88/291.53	   POL(c6(x_1)) = x_1
336.88/291.53	   POL(cons(x_1, x_2)) = [1] + x_2
336.88/291.53	   POL(plus(x_1, x_2)) = [1] + x_1 + x_2
336.88/291.53	   POL(s(x_1)) = x_1
336.88/291.53	
336.88/291.53	----------------------------------------
336.88/291.53	
336.88/291.53	(12)
336.88/291.53	Obligation:
336.88/291.53	Complexity Dependency Tuples Problem
336.88/291.53	
336.88/291.53	Rules:
336.88/291.53	   plus(0, z0) -> z0
336.88/291.53	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.53	Tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.53	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	S tuples:
336.88/291.53	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.53	K tuples:
336.88/291.53	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.54	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.54	Defined Rule Symbols:   plus_2
336.88/291.54	
336.88/291.54	Defined Pair Symbols:   APP_2, SUM_1, PLUS_2
336.88/291.54	
336.88/291.54	Compound Symbols:   c2_1, c4_2, c6_1
336.88/291.54	
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
336.88/291.54	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
336.88/291.54	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.54	We considered the (Usable) Rules:
336.88/291.54	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.54	   plus(0, z0) -> z0
336.88/291.54	And the Tuples:
336.88/291.54	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.54	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.54	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.54	The order we found is given by the following interpretation:
336.88/291.54	
336.88/291.54	Polynomial interpretation :
336.88/291.54	
336.88/291.54	   POL(0) = [2]
336.88/291.54	   POL(APP(x_1, x_2)) = [2]x_1 + [2]x_1*x_2 + [2]x_1^2
336.88/291.54	   POL(PLUS(x_1, x_2)) = x_1
336.88/291.54	   POL(SUM(x_1)) = [2]x_1^2
336.88/291.54	   POL(c2(x_1)) = x_1
336.88/291.54	   POL(c4(x_1, x_2)) = x_1 + x_2
336.88/291.54	   POL(c6(x_1)) = x_1
336.88/291.54	   POL(cons(x_1, x_2)) = [2] + x_1 + x_2
336.88/291.54	   POL(plus(x_1, x_2)) = x_1 + x_2
336.88/291.54	   POL(s(x_1)) = [1] + x_1
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(14)
336.88/291.54	Obligation:
336.88/291.54	Complexity Dependency Tuples Problem
336.88/291.54	
336.88/291.54	Rules:
336.88/291.54	   plus(0, z0) -> z0
336.88/291.54	   plus(s(z0), z1) -> s(plus(z0, z1))
336.88/291.54	Tuples:
336.88/291.54	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.54	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.54	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.54	S tuples:none
336.88/291.54	K tuples:
336.88/291.54	   APP(cons(z0, z1), z2) -> c2(APP(z1, z2))
336.88/291.54	   SUM(cons(z0, cons(z1, z2))) -> c4(SUM(cons(plus(z0, z1), z2)), PLUS(z0, z1))
336.88/291.54	   PLUS(s(z0), z1) -> c6(PLUS(z0, z1))
336.88/291.54	Defined Rule Symbols:   plus_2
336.88/291.54	
336.88/291.54	Defined Pair Symbols:   APP_2, SUM_1, PLUS_2
336.88/291.54	
336.88/291.54	Compound Symbols:   c2_1, c4_2, c6_1
336.88/291.54	
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(15) SIsEmptyProof (BOTH BOUNDS(ID, ID))
336.88/291.54	The set S is empty
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(16)
336.88/291.54	BOUNDS(1, 1)
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(17) RenamingProof (BOTH BOUNDS(ID, ID))
336.88/291.54	Renamed function symbols to avoid clashes with predefined symbol.
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(18)
336.88/291.54	Obligation:
336.88/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
336.88/291.54	
336.88/291.54	
336.88/291.54	The TRS R consists of the following rules:
336.88/291.54	
336.88/291.54	   app(nil, k) -> k
336.88/291.54	   app(l, nil) -> l
336.88/291.54	   app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.54	   sum(cons(x, nil)) -> cons(x, nil)
336.88/291.54	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.54	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.54	   plus(0', y) -> y
336.88/291.54	   plus(s(x), y) -> s(plus(x, y))
336.88/291.54	   sum(plus(cons(0', x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.54	   pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.54	
336.88/291.54	S is empty.
336.88/291.54	Rewrite Strategy: FULL
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(19) TypeInferenceProof (BOTH BOUNDS(ID, ID))
336.88/291.54	Infered types.
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(20)
336.88/291.54	Obligation:
336.88/291.54	TRS:
336.88/291.54	Rules:
336.88/291.54	app(nil, k) -> k
336.88/291.54	app(l, nil) -> l
336.88/291.54	app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.54	sum(cons(x, nil)) -> cons(x, nil)
336.88/291.54	sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.54	sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.54	plus(0', y) -> y
336.88/291.54	plus(s(x), y) -> s(plus(x, y))
336.88/291.54	sum(plus(cons(0', x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.54	pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.54	
336.88/291.54	Types:
336.88/291.54	app :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	nil :: nil:cons:0':s
336.88/291.54	cons :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	sum :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	plus :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	0' :: nil:cons:0':s
336.88/291.54	s :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	pred :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	hole_nil:cons:0':s1_0 :: nil:cons:0':s
336.88/291.54	gen_nil:cons:0':s2_0 :: Nat -> nil:cons:0':s
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(21) OrderProof (LOWER BOUND(ID))
336.88/291.54	Heuristically decided to analyse the following defined symbols:
336.88/291.54	app, sum, plus
336.88/291.54	
336.88/291.54	They will be analysed ascendingly in the following order:
336.88/291.54	app < sum
336.88/291.54	plus < sum
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(22)
336.88/291.54	Obligation:
336.88/291.54	TRS:
336.88/291.54	Rules:
336.88/291.54	app(nil, k) -> k
336.88/291.54	app(l, nil) -> l
336.88/291.54	app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.54	sum(cons(x, nil)) -> cons(x, nil)
336.88/291.54	sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.54	sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.54	plus(0', y) -> y
336.88/291.54	plus(s(x), y) -> s(plus(x, y))
336.88/291.54	sum(plus(cons(0', x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.54	pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.54	
336.88/291.54	Types:
336.88/291.54	app :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	nil :: nil:cons:0':s
336.88/291.54	cons :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	sum :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	plus :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	0' :: nil:cons:0':s
336.88/291.54	s :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	pred :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	hole_nil:cons:0':s1_0 :: nil:cons:0':s
336.88/291.54	gen_nil:cons:0':s2_0 :: Nat -> nil:cons:0':s
336.88/291.54	
336.88/291.54	
336.88/291.54	Generator Equations:
336.88/291.54	gen_nil:cons:0':s2_0(0) <=> nil
336.88/291.54	gen_nil:cons:0':s2_0(+(x, 1)) <=> cons(nil, gen_nil:cons:0':s2_0(x))
336.88/291.54	
336.88/291.54	
336.88/291.54	The following defined symbols remain to be analysed:
336.88/291.54	app, sum, plus
336.88/291.54	
336.88/291.54	They will be analysed ascendingly in the following order:
336.88/291.54	app < sum
336.88/291.54	plus < sum
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(23) RewriteLemmaProof (LOWER BOUND(ID))
336.88/291.54	Proved the following rewrite lemma:
336.88/291.54	app(gen_nil:cons:0':s2_0(n4_0), gen_nil:cons:0':s2_0(b)) -> gen_nil:cons:0':s2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
336.88/291.54	
336.88/291.54	Induction Base:
336.88/291.54	app(gen_nil:cons:0':s2_0(0), gen_nil:cons:0':s2_0(b)) ->_R^Omega(1)
336.88/291.54	gen_nil:cons:0':s2_0(b)
336.88/291.54	
336.88/291.54	Induction Step:
336.88/291.54	app(gen_nil:cons:0':s2_0(+(n4_0, 1)), gen_nil:cons:0':s2_0(b)) ->_R^Omega(1)
336.88/291.54	cons(nil, app(gen_nil:cons:0':s2_0(n4_0), gen_nil:cons:0':s2_0(b))) ->_IH
336.88/291.54	cons(nil, gen_nil:cons:0':s2_0(+(b, c5_0)))
336.88/291.54	
336.88/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(24)
336.88/291.54	Complex Obligation (BEST)
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(25)
336.88/291.54	Obligation:
336.88/291.54	Proved the lower bound n^1 for the following obligation:
336.88/291.54	
336.88/291.54	TRS:
336.88/291.54	Rules:
336.88/291.54	app(nil, k) -> k
336.88/291.54	app(l, nil) -> l
336.88/291.54	app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.54	sum(cons(x, nil)) -> cons(x, nil)
336.88/291.54	sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.54	sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.54	plus(0', y) -> y
336.88/291.54	plus(s(x), y) -> s(plus(x, y))
336.88/291.54	sum(plus(cons(0', x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.54	pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.54	
336.88/291.54	Types:
336.88/291.54	app :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	nil :: nil:cons:0':s
336.88/291.54	cons :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	sum :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	plus :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	0' :: nil:cons:0':s
336.88/291.54	s :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	pred :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	hole_nil:cons:0':s1_0 :: nil:cons:0':s
336.88/291.54	gen_nil:cons:0':s2_0 :: Nat -> nil:cons:0':s
336.88/291.54	
336.88/291.54	
336.88/291.54	Generator Equations:
336.88/291.54	gen_nil:cons:0':s2_0(0) <=> nil
336.88/291.54	gen_nil:cons:0':s2_0(+(x, 1)) <=> cons(nil, gen_nil:cons:0':s2_0(x))
336.88/291.54	
336.88/291.54	
336.88/291.54	The following defined symbols remain to be analysed:
336.88/291.54	app, sum, plus
336.88/291.54	
336.88/291.54	They will be analysed ascendingly in the following order:
336.88/291.54	app < sum
336.88/291.54	plus < sum
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(26) LowerBoundPropagationProof (FINISHED)
336.88/291.54	Propagated lower bound.
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(27)
336.88/291.54	BOUNDS(n^1, INF)
336.88/291.54	
336.88/291.54	----------------------------------------
336.88/291.54	
336.88/291.54	(28)
336.88/291.54	Obligation:
336.88/291.54	TRS:
336.88/291.54	Rules:
336.88/291.54	app(nil, k) -> k
336.88/291.54	app(l, nil) -> l
336.88/291.54	app(cons(x, l), k) -> cons(x, app(l, k))
336.88/291.54	sum(cons(x, nil)) -> cons(x, nil)
336.88/291.54	sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
336.88/291.54	sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
336.88/291.54	plus(0', y) -> y
336.88/291.54	plus(s(x), y) -> s(plus(x, y))
336.88/291.54	sum(plus(cons(0', x), cons(y, l))) -> pred(sum(cons(s(x), cons(y, l))))
336.88/291.54	pred(cons(s(x), nil)) -> cons(x, nil)
336.88/291.54	
336.88/291.54	Types:
336.88/291.54	app :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	nil :: nil:cons:0':s
336.88/291.54	cons :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	sum :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	plus :: nil:cons:0':s -> nil:cons:0':s -> nil:cons:0':s
336.88/291.54	0' :: nil:cons:0':s
336.88/291.54	s :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	pred :: nil:cons:0':s -> nil:cons:0':s
336.88/291.54	hole_nil:cons:0':s1_0 :: nil:cons:0':s
336.88/291.54	gen_nil:cons:0':s2_0 :: Nat -> nil:cons:0':s
336.88/291.54	
336.88/291.54	
336.88/291.54	Lemmas:
336.88/291.54	app(gen_nil:cons:0':s2_0(n4_0), gen_nil:cons:0':s2_0(b)) -> gen_nil:cons:0':s2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
336.88/291.54	
336.88/291.54	
336.88/291.54	Generator Equations:
336.88/291.54	gen_nil:cons:0':s2_0(0) <=> nil
336.88/291.54	gen_nil:cons:0':s2_0(+(x, 1)) <=> cons(nil, gen_nil:cons:0':s2_0(x))
336.88/291.54	
336.88/291.54	
336.88/291.54	The following defined symbols remain to be analysed:
336.88/291.54	plus, sum
336.88/291.54	
336.88/291.54	They will be analysed ascendingly in the following order:
336.88/291.54	plus < sum
337.00/291.59	EOF