11.35/3.70	WORST_CASE(Omega(n^2), O(n^2))
11.35/3.71	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
11.35/3.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.35/3.71	
11.35/3.71	
11.35/3.71	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).
11.35/3.71	
11.35/3.71	(0) CpxTRS
11.35/3.71	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
11.35/3.71	(2) CdtProblem
11.35/3.71	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
11.35/3.71	    (4) CdtProblem
11.35/3.71	    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
11.35/3.71	    (6) CdtProblem
11.35/3.71	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms]
11.35/3.71	    (8) CdtProblem
11.35/3.71	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 43 ms]
11.35/3.71	    (10) CdtProblem
11.35/3.71	    (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
11.35/3.71	    (12) BOUNDS(1, 1)
11.35/3.71	(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
11.35/3.71	(14) CpxTRS
11.35/3.71	    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
11.35/3.71	    (16) typed CpxTrs
11.35/3.71	    (17) OrderProof [LOWER BOUND(ID), 0 ms]
11.35/3.71	    (18) typed CpxTrs
11.35/3.71	    (19) RewriteLemmaProof [LOWER BOUND(ID), 307 ms]
11.35/3.71	    (20) BEST
11.35/3.71	        (21) proven lower bound
11.35/3.71	            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
11.35/3.71	            (23) BOUNDS(n^1, INF)
11.35/3.71	        (24) typed CpxTrs
11.35/3.71	            (25) RewriteLemmaProof [LOWER BOUND(ID), 49 ms]
11.35/3.71	            (26) proven lower bound
11.35/3.71	            (27) LowerBoundPropagationProof [FINISHED, 0 ms]
11.35/3.71	            (28) BOUNDS(n^2, INF)
11.35/3.71	
11.35/3.71	
11.35/3.71	----------------------------------------
11.35/3.71	
11.35/3.71	(0)
11.35/3.71	Obligation:
11.35/3.71	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).
11.35/3.71	
11.35/3.71	
11.35/3.71	The TRS R consists of the following rules:
11.35/3.71	
11.35/3.71	   rev(nil) -> nil
11.35/3.71	   rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.71	   car(.(x, y)) -> x
11.35/3.71	   cdr(.(x, y)) -> y
11.35/3.71	   null(nil) -> true
11.35/3.71	   null(.(x, y)) -> false
11.35/3.71	   ++(nil, y) -> y
11.35/3.71	   ++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.71	
11.35/3.71	S is empty.
11.35/3.71	Rewrite Strategy: INNERMOST
11.35/3.71	----------------------------------------
11.35/3.71	
11.35/3.71	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
11.35/3.71	Converted Cpx (relative) TRS to CDT
11.35/3.71	----------------------------------------
11.35/3.71	
11.35/3.71	(2)
11.35/3.71	Obligation:
11.35/3.71	Complexity Dependency Tuples Problem
11.35/3.71	
11.35/3.71	Rules:
11.35/3.71	   rev(nil) -> nil
11.35/3.71	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   car(.(z0, z1)) -> z0
11.35/3.72	   cdr(.(z0, z1)) -> z1
11.35/3.72	   null(nil) -> true
11.35/3.72	   null(.(z0, z1)) -> false
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	Tuples:
11.35/3.72	   REV(nil) -> c
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   CAR(.(z0, z1)) -> c2
11.35/3.72	   CDR(.(z0, z1)) -> c3
11.35/3.72	   NULL(nil) -> c4
11.35/3.72	   NULL(.(z0, z1)) -> c5
11.35/3.72	   ++'(nil, z0) -> c6
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	S tuples:
11.35/3.72	   REV(nil) -> c
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   CAR(.(z0, z1)) -> c2
11.35/3.72	   CDR(.(z0, z1)) -> c3
11.35/3.72	   NULL(nil) -> c4
11.35/3.72	   NULL(.(z0, z1)) -> c5
11.35/3.72	   ++'(nil, z0) -> c6
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	K tuples:none
11.35/3.72	Defined Rule Symbols:   rev_1, car_1, cdr_1, null_1, ++_2
11.35/3.72	
11.35/3.72	Defined Pair Symbols:   REV_1, CAR_1, CDR_1, NULL_1, ++'_2
11.35/3.72	
11.35/3.72	Compound Symbols:   c, c1_2, c2, c3, c4, c5, c6, c7_1
11.35/3.72	
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
11.35/3.72	Removed 6 trailing nodes:
11.35/3.72	   ++'(nil, z0) -> c6
11.35/3.72	   CAR(.(z0, z1)) -> c2
11.35/3.72	   NULL(.(z0, z1)) -> c5
11.35/3.72	   REV(nil) -> c
11.35/3.72	   NULL(nil) -> c4
11.35/3.72	   CDR(.(z0, z1)) -> c3
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(4)
11.35/3.72	Obligation:
11.35/3.72	Complexity Dependency Tuples Problem
11.35/3.72	
11.35/3.72	Rules:
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   car(.(z0, z1)) -> z0
11.35/3.72	   cdr(.(z0, z1)) -> z1
11.35/3.72	   null(nil) -> true
11.35/3.72	   null(.(z0, z1)) -> false
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	S tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	K tuples:none
11.35/3.72	Defined Rule Symbols:   rev_1, car_1, cdr_1, null_1, ++_2
11.35/3.72	
11.35/3.72	Defined Pair Symbols:   REV_1, ++'_2
11.35/3.72	
11.35/3.72	Compound Symbols:   c1_2, c7_1
11.35/3.72	
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
11.35/3.72	The following rules are not usable and were removed:
11.35/3.72	   car(.(z0, z1)) -> z0
11.35/3.72	   cdr(.(z0, z1)) -> z1
11.35/3.72	   null(nil) -> true
11.35/3.72	   null(.(z0, z1)) -> false
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(6)
11.35/3.72	Obligation:
11.35/3.72	Complexity Dependency Tuples Problem
11.35/3.72	
11.35/3.72	Rules:
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	S tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	K tuples:none
11.35/3.72	Defined Rule Symbols:   rev_1, ++_2
11.35/3.72	
11.35/3.72	Defined Pair Symbols:   REV_1, ++'_2
11.35/3.72	
11.35/3.72	Compound Symbols:   c1_2, c7_1
11.35/3.72	
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
11.35/3.72	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	We considered the (Usable) Rules:none
11.35/3.72	And the Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	The order we found is given by the following interpretation:
11.35/3.72	
11.35/3.72	Polynomial interpretation :
11.35/3.72	
11.35/3.72	   POL(++(x_1, x_2)) = x_1 + x_2
11.35/3.72	   POL(++'(x_1, x_2)) = 0
11.35/3.72	   POL(.(x_1, x_2)) = [1] + x_1 + x_2
11.35/3.72	   POL(REV(x_1)) = x_1
11.35/3.72	   POL(c1(x_1, x_2)) = x_1 + x_2
11.35/3.72	   POL(c7(x_1)) = x_1
11.35/3.72	   POL(nil) = 0
11.35/3.72	   POL(rev(x_1)) = [1] + x_1
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(8)
11.35/3.72	Obligation:
11.35/3.72	Complexity Dependency Tuples Problem
11.35/3.72	
11.35/3.72	Rules:
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	S tuples:
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	K tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	Defined Rule Symbols:   rev_1, ++_2
11.35/3.72	
11.35/3.72	Defined Pair Symbols:   REV_1, ++'_2
11.35/3.72	
11.35/3.72	Compound Symbols:   c1_2, c7_1
11.35/3.72	
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
11.35/3.72	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	We considered the (Usable) Rules:
11.35/3.72	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	And the Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	The order we found is given by the following interpretation:
11.35/3.72	
11.35/3.72	Polynomial interpretation :
11.35/3.72	
11.35/3.72	   POL(++(x_1, x_2)) = x_1 + [2]x_2
11.35/3.72	   POL(++'(x_1, x_2)) = [2]x_1
11.35/3.72	   POL(.(x_1, x_2)) = [2] + x_2
11.35/3.72	   POL(REV(x_1)) = x_1^2
11.35/3.72	   POL(c1(x_1, x_2)) = x_1 + x_2
11.35/3.72	   POL(c7(x_1)) = x_1
11.35/3.72	   POL(nil) = 0
11.35/3.72	   POL(rev(x_1)) = [2]x_1
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(10)
11.35/3.72	Obligation:
11.35/3.72	Complexity Dependency Tuples Problem
11.35/3.72	
11.35/3.72	Rules:
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
11.35/3.72	   ++(nil, z0) -> z0
11.35/3.72	   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
11.35/3.72	Tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	S tuples:none
11.35/3.72	K tuples:
11.35/3.72	   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
11.35/3.72	   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
11.35/3.72	Defined Rule Symbols:   rev_1, ++_2
11.35/3.72	
11.35/3.72	Defined Pair Symbols:   REV_1, ++'_2
11.35/3.72	
11.35/3.72	Compound Symbols:   c1_2, c7_1
11.35/3.72	
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(11) SIsEmptyProof (BOTH BOUNDS(ID, ID))
11.35/3.72	The set S is empty
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(12)
11.35/3.72	BOUNDS(1, 1)
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(13) RenamingProof (BOTH BOUNDS(ID, ID))
11.35/3.72	Renamed function symbols to avoid clashes with predefined symbol.
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(14)
11.35/3.72	Obligation:
11.35/3.72	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
11.35/3.72	
11.35/3.72	
11.35/3.72	The TRS R consists of the following rules:
11.35/3.72	
11.35/3.72	   rev(nil) -> nil
11.35/3.72	   rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	   car(.(x, y)) -> x
11.35/3.72	   cdr(.(x, y)) -> y
11.35/3.72	   null(nil) -> true
11.35/3.72	   null(.(x, y)) -> false
11.35/3.72	   ++(nil, y) -> y
11.35/3.72	   ++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	S is empty.
11.35/3.72	Rewrite Strategy: INNERMOST
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
11.35/3.72	Infered types.
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(16)
11.35/3.72	Obligation:
11.35/3.72	Innermost TRS:
11.35/3.72	Rules:
11.35/3.72	rev(nil) -> nil
11.35/3.72	rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	car(.(x, y)) -> x
11.35/3.72	cdr(.(x, y)) -> y
11.35/3.72	null(nil) -> true
11.35/3.72	null(.(x, y)) -> false
11.35/3.72	++(nil, y) -> y
11.35/3.72	++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	Types:
11.35/3.72	rev :: nil:. -> nil:.
11.35/3.72	nil :: nil:.
11.35/3.72	. :: car -> nil:. -> nil:.
11.35/3.72	++ :: nil:. -> nil:. -> nil:.
11.35/3.72	car :: nil:. -> car
11.35/3.72	cdr :: nil:. -> nil:.
11.35/3.72	null :: nil:. -> true:false
11.35/3.72	true :: true:false
11.35/3.72	false :: true:false
11.35/3.72	hole_nil:.1_0 :: nil:.
11.35/3.72	hole_car2_0 :: car
11.35/3.72	hole_true:false3_0 :: true:false
11.35/3.72	gen_nil:.4_0 :: Nat -> nil:.
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(17) OrderProof (LOWER BOUND(ID))
11.35/3.72	Heuristically decided to analyse the following defined symbols:
11.35/3.72	rev, ++
11.35/3.72	
11.35/3.72	They will be analysed ascendingly in the following order:
11.35/3.72	++ < rev
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(18)
11.35/3.72	Obligation:
11.35/3.72	Innermost TRS:
11.35/3.72	Rules:
11.35/3.72	rev(nil) -> nil
11.35/3.72	rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	car(.(x, y)) -> x
11.35/3.72	cdr(.(x, y)) -> y
11.35/3.72	null(nil) -> true
11.35/3.72	null(.(x, y)) -> false
11.35/3.72	++(nil, y) -> y
11.35/3.72	++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	Types:
11.35/3.72	rev :: nil:. -> nil:.
11.35/3.72	nil :: nil:.
11.35/3.72	. :: car -> nil:. -> nil:.
11.35/3.72	++ :: nil:. -> nil:. -> nil:.
11.35/3.72	car :: nil:. -> car
11.35/3.72	cdr :: nil:. -> nil:.
11.35/3.72	null :: nil:. -> true:false
11.35/3.72	true :: true:false
11.35/3.72	false :: true:false
11.35/3.72	hole_nil:.1_0 :: nil:.
11.35/3.72	hole_car2_0 :: car
11.35/3.72	hole_true:false3_0 :: true:false
11.35/3.72	gen_nil:.4_0 :: Nat -> nil:.
11.35/3.72	
11.35/3.72	
11.35/3.72	Generator Equations:
11.35/3.72	gen_nil:.4_0(0) <=> nil
11.35/3.72	gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))
11.35/3.72	
11.35/3.72	
11.35/3.72	The following defined symbols remain to be analysed:
11.35/3.72	++, rev
11.35/3.72	
11.35/3.72	They will be analysed ascendingly in the following order:
11.35/3.72	++ < rev
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(19) RewriteLemmaProof (LOWER BOUND(ID))
11.35/3.72	Proved the following rewrite lemma:
11.35/3.72	++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
11.35/3.72	
11.35/3.72	Induction Base:
11.35/3.72	++(gen_nil:.4_0(0), gen_nil:.4_0(b)) ->_R^Omega(1)
11.35/3.72	gen_nil:.4_0(b)
11.35/3.72	
11.35/3.72	Induction Step:
11.35/3.72	++(gen_nil:.4_0(+(n6_0, 1)), gen_nil:.4_0(b)) ->_R^Omega(1)
11.35/3.72	.(hole_car2_0, ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b))) ->_IH
11.35/3.72	.(hole_car2_0, gen_nil:.4_0(+(b, c7_0)))
11.35/3.72	
11.35/3.72	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(20)
11.35/3.72	Complex Obligation (BEST)
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(21)
11.35/3.72	Obligation:
11.35/3.72	Proved the lower bound n^1 for the following obligation:
11.35/3.72	
11.35/3.72	Innermost TRS:
11.35/3.72	Rules:
11.35/3.72	rev(nil) -> nil
11.35/3.72	rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	car(.(x, y)) -> x
11.35/3.72	cdr(.(x, y)) -> y
11.35/3.72	null(nil) -> true
11.35/3.72	null(.(x, y)) -> false
11.35/3.72	++(nil, y) -> y
11.35/3.72	++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	Types:
11.35/3.72	rev :: nil:. -> nil:.
11.35/3.72	nil :: nil:.
11.35/3.72	. :: car -> nil:. -> nil:.
11.35/3.72	++ :: nil:. -> nil:. -> nil:.
11.35/3.72	car :: nil:. -> car
11.35/3.72	cdr :: nil:. -> nil:.
11.35/3.72	null :: nil:. -> true:false
11.35/3.72	true :: true:false
11.35/3.72	false :: true:false
11.35/3.72	hole_nil:.1_0 :: nil:.
11.35/3.72	hole_car2_0 :: car
11.35/3.72	hole_true:false3_0 :: true:false
11.35/3.72	gen_nil:.4_0 :: Nat -> nil:.
11.35/3.72	
11.35/3.72	
11.35/3.72	Generator Equations:
11.35/3.72	gen_nil:.4_0(0) <=> nil
11.35/3.72	gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))
11.35/3.72	
11.35/3.72	
11.35/3.72	The following defined symbols remain to be analysed:
11.35/3.72	++, rev
11.35/3.72	
11.35/3.72	They will be analysed ascendingly in the following order:
11.35/3.72	++ < rev
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(22) LowerBoundPropagationProof (FINISHED)
11.35/3.72	Propagated lower bound.
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(23)
11.35/3.72	BOUNDS(n^1, INF)
11.35/3.72	
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(24)
11.35/3.72	Obligation:
11.35/3.72	Innermost TRS:
11.35/3.72	Rules:
11.35/3.72	rev(nil) -> nil
11.35/3.72	rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	car(.(x, y)) -> x
11.35/3.72	cdr(.(x, y)) -> y
11.35/3.72	null(nil) -> true
11.35/3.72	null(.(x, y)) -> false
11.35/3.72	++(nil, y) -> y
11.35/3.72	++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	Types:
11.35/3.72	rev :: nil:. -> nil:.
11.35/3.72	nil :: nil:.
11.35/3.72	. :: car -> nil:. -> nil:.
11.35/3.72	++ :: nil:. -> nil:. -> nil:.
11.35/3.72	car :: nil:. -> car
11.35/3.72	cdr :: nil:. -> nil:.
11.35/3.72	null :: nil:. -> true:false
11.35/3.72	true :: true:false
11.35/3.72	false :: true:false
11.35/3.72	hole_nil:.1_0 :: nil:.
11.35/3.72	hole_car2_0 :: car
11.35/3.72	hole_true:false3_0 :: true:false
11.35/3.72	gen_nil:.4_0 :: Nat -> nil:.
11.35/3.72	
11.35/3.72	
11.35/3.72	Lemmas:
11.35/3.72	++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
11.35/3.72	
11.35/3.72	
11.35/3.72	Generator Equations:
11.35/3.72	gen_nil:.4_0(0) <=> nil
11.35/3.72	gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))
11.35/3.72	
11.35/3.72	
11.35/3.72	The following defined symbols remain to be analysed:
11.35/3.72	rev
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(25) RewriteLemmaProof (LOWER BOUND(ID))
11.35/3.72	Proved the following rewrite lemma:
11.35/3.72	rev(gen_nil:.4_0(n535_0)) -> gen_nil:.4_0(n535_0), rt in Omega(1 + n535_0 + n535_0^2)
11.35/3.72	
11.35/3.72	Induction Base:
11.35/3.72	rev(gen_nil:.4_0(0)) ->_R^Omega(1)
11.35/3.72	nil
11.35/3.72	
11.35/3.72	Induction Step:
11.35/3.72	rev(gen_nil:.4_0(+(n535_0, 1))) ->_R^Omega(1)
11.35/3.72	++(rev(gen_nil:.4_0(n535_0)), .(hole_car2_0, nil)) ->_IH
11.35/3.72	++(gen_nil:.4_0(c536_0), .(hole_car2_0, nil)) ->_L^Omega(1 + n535_0)
11.35/3.72	gen_nil:.4_0(+(n535_0, +(0, 1)))
11.35/3.72	
11.35/3.72	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(26)
11.35/3.72	Obligation:
11.35/3.72	Proved the lower bound n^2 for the following obligation:
11.35/3.72	
11.35/3.72	Innermost TRS:
11.35/3.72	Rules:
11.35/3.72	rev(nil) -> nil
11.35/3.72	rev(.(x, y)) -> ++(rev(y), .(x, nil))
11.35/3.72	car(.(x, y)) -> x
11.35/3.72	cdr(.(x, y)) -> y
11.35/3.72	null(nil) -> true
11.35/3.72	null(.(x, y)) -> false
11.35/3.72	++(nil, y) -> y
11.35/3.72	++(.(x, y), z) -> .(x, ++(y, z))
11.35/3.72	
11.35/3.72	Types:
11.35/3.72	rev :: nil:. -> nil:.
11.35/3.72	nil :: nil:.
11.35/3.72	. :: car -> nil:. -> nil:.
11.35/3.72	++ :: nil:. -> nil:. -> nil:.
11.35/3.72	car :: nil:. -> car
11.35/3.72	cdr :: nil:. -> nil:.
11.35/3.72	null :: nil:. -> true:false
11.35/3.72	true :: true:false
11.35/3.72	false :: true:false
11.35/3.72	hole_nil:.1_0 :: nil:.
11.35/3.72	hole_car2_0 :: car
11.35/3.72	hole_true:false3_0 :: true:false
11.35/3.72	gen_nil:.4_0 :: Nat -> nil:.
11.35/3.72	
11.35/3.72	
11.35/3.72	Lemmas:
11.35/3.72	++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
11.35/3.72	
11.35/3.72	
11.35/3.72	Generator Equations:
11.35/3.72	gen_nil:.4_0(0) <=> nil
11.35/3.72	gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))
11.35/3.72	
11.35/3.72	
11.35/3.72	The following defined symbols remain to be analysed:
11.35/3.72	rev
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(27) LowerBoundPropagationProof (FINISHED)
11.35/3.72	Propagated lower bound.
11.35/3.72	----------------------------------------
11.35/3.72	
11.35/3.72	(28)
11.35/3.72	BOUNDS(n^2, INF)
11.64/3.75	EOF