14.14/4.55	WORST_CASE(Omega(n^1), O(n^1))
14.14/4.56	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
14.14/4.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.14/4.56	
14.14/4.56	
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	(0) CpxRelTRS
14.14/4.56	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 140 ms]
14.14/4.56	(2) CpxRelTRS
14.14/4.56	(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
14.14/4.56	(4) CdtProblem
14.14/4.56	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (6) CdtProblem
14.14/4.56	    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (8) CdtProblem
14.14/4.56	    (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (10) CdtProblem
14.14/4.56	    (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
14.14/4.56	    (12) CdtProblem
14.14/4.56	    (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (14) CdtProblem
14.14/4.56	    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 16 ms]
14.14/4.56	    (16) CdtProblem
14.14/4.56	    (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (18) BOUNDS(1, 1)
14.14/4.56	(19) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	(20) CpxRelTRS
14.14/4.56	    (21) SlicingProof [LOWER BOUND(ID), 0 ms]
14.14/4.56	    (22) CpxRelTRS
14.14/4.56	    (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (24) typed CpxTrs
14.14/4.56	    (25) OrderProof [LOWER BOUND(ID), 0 ms]
14.14/4.56	    (26) typed CpxTrs
14.14/4.56	    (27) RewriteLemmaProof [LOWER BOUND(ID), 299 ms]
14.14/4.56	    (28) BEST
14.14/4.56	        (29) proven lower bound
14.14/4.56	            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
14.14/4.56	            (31) BOUNDS(n^1, INF)
14.14/4.56	        (32) typed CpxTrs
14.14/4.56	            (33) RewriteLemmaProof [LOWER BOUND(ID), 49 ms]
14.14/4.56	            (34) BOUNDS(1, INF)
14.14/4.56	
14.14/4.56	
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(0)
14.14/4.56	Obligation:
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	
14.14/4.56	The TRS R consists of the following rules:
14.14/4.56	
14.14/4.56	   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
14.14/4.56	   lte(Cons(x, xs), Nil) -> False
14.14/4.56	   even(Cons(x, Nil)) -> False
14.14/4.56	   even(Cons(x', Cons(x, xs))) -> even(xs)
14.14/4.56	   notEmpty(Cons(x, xs)) -> True
14.14/4.56	   notEmpty(Nil) -> False
14.14/4.56	   lte(Nil, y) -> True
14.14/4.56	   even(Nil) -> True
14.14/4.56	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.56	
14.14/4.56	The (relative) TRS S consists of the following rules:
14.14/4.56	
14.14/4.56	   and(False, False) -> False
14.14/4.56	   and(True, False) -> False
14.14/4.56	   and(False, True) -> False
14.14/4.56	   and(True, True) -> True
14.14/4.56	
14.14/4.56	Rewrite Strategy: INNERMOST
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
14.14/4.56	proved termination of relative rules
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(2)
14.14/4.56	Obligation:
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	
14.14/4.56	The TRS R consists of the following rules:
14.14/4.56	
14.14/4.56	   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
14.14/4.56	   lte(Cons(x, xs), Nil) -> False
14.14/4.56	   even(Cons(x, Nil)) -> False
14.14/4.56	   even(Cons(x', Cons(x, xs))) -> even(xs)
14.14/4.56	   notEmpty(Cons(x, xs)) -> True
14.14/4.56	   notEmpty(Nil) -> False
14.14/4.56	   lte(Nil, y) -> True
14.14/4.56	   even(Nil) -> True
14.14/4.56	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.56	
14.14/4.56	The (relative) TRS S consists of the following rules:
14.14/4.56	
14.14/4.56	   and(False, False) -> False
14.14/4.56	   and(True, False) -> False
14.14/4.56	   and(False, True) -> False
14.14/4.56	   and(True, True) -> True
14.14/4.56	
14.14/4.56	Rewrite Strategy: INNERMOST
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
14.14/4.57	Converted Cpx (relative) TRS to CDT
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(4)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	Tuples:
14.14/4.57	   AND(False, False) -> c
14.14/4.57	   AND(True, False) -> c1
14.14/4.57	   AND(False, True) -> c2
14.14/4.57	   AND(True, True) -> c3
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   LTE(Cons(z0, z1), Nil) -> c5
14.14/4.57	   LTE(Nil, z0) -> c6
14.14/4.57	   EVEN(Cons(z0, Nil)) -> c7
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   EVEN(Nil) -> c9
14.14/4.57	   NOTEMPTY(Cons(z0, z1)) -> c10
14.14/4.57	   NOTEMPTY(Nil) -> c11
14.14/4.57	   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   LTE(Cons(z0, z1), Nil) -> c5
14.14/4.57	   LTE(Nil, z0) -> c6
14.14/4.57	   EVEN(Cons(z0, Nil)) -> c7
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   EVEN(Nil) -> c9
14.14/4.57	   NOTEMPTY(Cons(z0, z1)) -> c10
14.14/4.57	   NOTEMPTY(Nil) -> c11
14.14/4.57	   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   AND_2, LTE_2, EVEN_1, NOTEMPTY_1, GOAL_2
14.14/4.57	
14.14/4.57	Compound Symbols:   c, c1, c2, c3, c4_1, c5, c6, c7, c8_1, c9, c10, c11, c12_3
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
14.14/4.57	Removed 10 trailing nodes:
14.14/4.57	   LTE(Cons(z0, z1), Nil) -> c5
14.14/4.57	   EVEN(Cons(z0, Nil)) -> c7
14.14/4.57	   EVEN(Nil) -> c9
14.14/4.57	   LTE(Nil, z0) -> c6
14.14/4.57	   NOTEMPTY(Nil) -> c11
14.14/4.57	   NOTEMPTY(Cons(z0, z1)) -> c10
14.14/4.57	   AND(False, True) -> c2
14.14/4.57	   AND(False, False) -> c
14.14/4.57	   AND(True, True) -> c3
14.14/4.57	   AND(True, False) -> c1
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(6)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1, c12_3
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
14.14/4.57	Removed 1 trailing tuple parts
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(8)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c12(LTE(z0, z1), EVEN(z0))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c12(LTE(z0, z1), EVEN(z0))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1, c12_2
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
14.14/4.57	Split RHS of tuples not part of any SCC
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(10)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c(LTE(z0, z1))
14.14/4.57	   GOAL(z0, z1) -> c(EVEN(z0))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	   GOAL(z0, z1) -> c(LTE(z0, z1))
14.14/4.57	   GOAL(z0, z1) -> c(EVEN(z0))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1, c_1
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(11) CdtLeafRemovalProof (ComplexityIfPolyImplication)
14.14/4.57	Removed 2 leading nodes:
14.14/4.57	   GOAL(z0, z1) -> c(LTE(z0, z1))
14.14/4.57	   GOAL(z0, z1) -> c(EVEN(z0))
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(12)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
14.14/4.57	The following rules are not usable and were removed:
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
14.14/4.57	   lte(Cons(z0, z1), Nil) -> False
14.14/4.57	   lte(Nil, z0) -> True
14.14/4.57	   even(Cons(z0, Nil)) -> False
14.14/4.57	   even(Cons(z0, Cons(z1, z2))) -> even(z2)
14.14/4.57	   even(Nil) -> True
14.14/4.57	   notEmpty(Cons(z0, z1)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   goal(z0, z1) -> and(lte(z0, z1), even(z0))
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(14)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:none
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	S tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	K tuples:none
14.14/4.57	Defined Rule Symbols:none
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
14.14/4.57	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	We considered the (Usable) Rules:none
14.14/4.57	And the Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	The order we found is given by the following interpretation:
14.14/4.57	
14.14/4.57	Polynomial interpretation :
14.14/4.57	
14.14/4.57	   POL(Cons(x_1, x_2)) = [1] + x_2
14.14/4.57	   POL(EVEN(x_1)) = x_1
14.14/4.57	   POL(LTE(x_1, x_2)) = x_1 + x_2
14.14/4.57	   POL(c4(x_1)) = x_1
14.14/4.57	   POL(c8(x_1)) = x_1
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(16)
14.14/4.57	Obligation:
14.14/4.57	Complexity Dependency Tuples Problem
14.14/4.57	
14.14/4.57	Rules:none
14.14/4.57	Tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	S tuples:none
14.14/4.57	K tuples:
14.14/4.57	   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
14.14/4.57	   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
14.14/4.57	Defined Rule Symbols:none
14.14/4.57	
14.14/4.57	Defined Pair Symbols:   LTE_2, EVEN_1
14.14/4.57	
14.14/4.57	Compound Symbols:   c4_1, c8_1
14.14/4.57	
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(17) SIsEmptyProof (BOTH BOUNDS(ID, ID))
14.14/4.57	The set S is empty
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(18)
14.14/4.57	BOUNDS(1, 1)
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(19) RenamingProof (BOTH BOUNDS(ID, ID))
14.14/4.57	Renamed function symbols to avoid clashes with predefined symbol.
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(20)
14.14/4.57	Obligation:
14.14/4.57	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
14.14/4.57	
14.14/4.57	
14.14/4.57	The TRS R consists of the following rules:
14.14/4.57	
14.14/4.57	   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
14.14/4.57	   lte(Cons(x, xs), Nil) -> False
14.14/4.57	   even(Cons(x, Nil)) -> False
14.14/4.57	   even(Cons(x', Cons(x, xs))) -> even(xs)
14.14/4.57	   notEmpty(Cons(x, xs)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   lte(Nil, y) -> True
14.14/4.57	   even(Nil) -> True
14.14/4.57	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	
14.14/4.57	The (relative) TRS S consists of the following rules:
14.14/4.57	
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	
14.14/4.57	Rewrite Strategy: INNERMOST
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(21) SlicingProof (LOWER BOUND(ID))
14.14/4.57	Sliced the following arguments:
14.14/4.57	Cons/0
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(22)
14.14/4.57	Obligation:
14.14/4.57	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
14.14/4.57	
14.14/4.57	
14.14/4.57	The TRS R consists of the following rules:
14.14/4.57	
14.14/4.57	   lte(Cons(xs'), Cons(xs)) -> lte(xs', xs)
14.14/4.57	   lte(Cons(xs), Nil) -> False
14.14/4.57	   even(Cons(Nil)) -> False
14.14/4.57	   even(Cons(Cons(xs))) -> even(xs)
14.14/4.57	   notEmpty(Cons(xs)) -> True
14.14/4.57	   notEmpty(Nil) -> False
14.14/4.57	   lte(Nil, y) -> True
14.14/4.57	   even(Nil) -> True
14.14/4.57	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	
14.14/4.57	The (relative) TRS S consists of the following rules:
14.14/4.57	
14.14/4.57	   and(False, False) -> False
14.14/4.57	   and(True, False) -> False
14.14/4.57	   and(False, True) -> False
14.14/4.57	   and(True, True) -> True
14.14/4.57	
14.14/4.57	Rewrite Strategy: INNERMOST
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(23) TypeInferenceProof (BOTH BOUNDS(ID, ID))
14.14/4.57	Infered types.
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(24)
14.14/4.57	Obligation:
14.14/4.57	Innermost TRS:
14.14/4.57	Rules:
14.14/4.57	lte(Cons(xs'), Cons(xs)) -> lte(xs', xs)
14.14/4.57	lte(Cons(xs), Nil) -> False
14.14/4.57	even(Cons(Nil)) -> False
14.14/4.57	even(Cons(Cons(xs))) -> even(xs)
14.14/4.57	notEmpty(Cons(xs)) -> True
14.14/4.57	notEmpty(Nil) -> False
14.14/4.57	lte(Nil, y) -> True
14.14/4.57	even(Nil) -> True
14.14/4.57	goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	and(False, False) -> False
14.14/4.57	and(True, False) -> False
14.14/4.57	and(False, True) -> False
14.14/4.57	and(True, True) -> True
14.14/4.57	
14.14/4.57	Types:
14.14/4.57	lte :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	Cons :: Cons:Nil -> Cons:Nil
14.14/4.57	Nil :: Cons:Nil
14.14/4.57	False :: False:True
14.14/4.57	even :: Cons:Nil -> False:True
14.14/4.57	notEmpty :: Cons:Nil -> False:True
14.14/4.57	True :: False:True
14.14/4.57	goal :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	and :: False:True -> False:True -> False:True
14.14/4.57	hole_False:True1_0 :: False:True
14.14/4.57	hole_Cons:Nil2_0 :: Cons:Nil
14.14/4.57	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(25) OrderProof (LOWER BOUND(ID))
14.14/4.57	Heuristically decided to analyse the following defined symbols:
14.14/4.57	lte, even
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(26)
14.14/4.57	Obligation:
14.14/4.57	Innermost TRS:
14.14/4.57	Rules:
14.14/4.57	lte(Cons(xs'), Cons(xs)) -> lte(xs', xs)
14.14/4.57	lte(Cons(xs), Nil) -> False
14.14/4.57	even(Cons(Nil)) -> False
14.14/4.57	even(Cons(Cons(xs))) -> even(xs)
14.14/4.57	notEmpty(Cons(xs)) -> True
14.14/4.57	notEmpty(Nil) -> False
14.14/4.57	lte(Nil, y) -> True
14.14/4.57	even(Nil) -> True
14.14/4.57	goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	and(False, False) -> False
14.14/4.57	and(True, False) -> False
14.14/4.57	and(False, True) -> False
14.14/4.57	and(True, True) -> True
14.14/4.57	
14.14/4.57	Types:
14.14/4.57	lte :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	Cons :: Cons:Nil -> Cons:Nil
14.14/4.57	Nil :: Cons:Nil
14.14/4.57	False :: False:True
14.14/4.57	even :: Cons:Nil -> False:True
14.14/4.57	notEmpty :: Cons:Nil -> False:True
14.14/4.57	True :: False:True
14.14/4.57	goal :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	and :: False:True -> False:True -> False:True
14.14/4.57	hole_False:True1_0 :: False:True
14.14/4.57	hole_Cons:Nil2_0 :: Cons:Nil
14.14/4.57	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
14.14/4.57	
14.14/4.57	
14.14/4.57	Generator Equations:
14.14/4.57	gen_Cons:Nil3_0(0) <=> Nil
14.14/4.57	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
14.14/4.57	
14.14/4.57	
14.14/4.57	The following defined symbols remain to be analysed:
14.14/4.57	lte, even
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(27) RewriteLemmaProof (LOWER BOUND(ID))
14.14/4.57	Proved the following rewrite lemma:
14.14/4.57	lte(gen_Cons:Nil3_0(+(1, n5_0)), gen_Cons:Nil3_0(n5_0)) -> False, rt in Omega(1 + n5_0)
14.14/4.57	
14.14/4.57	Induction Base:
14.14/4.57	lte(gen_Cons:Nil3_0(+(1, 0)), gen_Cons:Nil3_0(0)) ->_R^Omega(1)
14.14/4.57	False
14.14/4.57	
14.14/4.57	Induction Step:
14.14/4.57	lte(gen_Cons:Nil3_0(+(1, +(n5_0, 1))), gen_Cons:Nil3_0(+(n5_0, 1))) ->_R^Omega(1)
14.14/4.57	lte(gen_Cons:Nil3_0(+(1, n5_0)), gen_Cons:Nil3_0(n5_0)) ->_IH
14.14/4.57	False
14.14/4.57	
14.14/4.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(28)
14.14/4.57	Complex Obligation (BEST)
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(29)
14.14/4.57	Obligation:
14.14/4.57	Proved the lower bound n^1 for the following obligation:
14.14/4.57	
14.14/4.57	Innermost TRS:
14.14/4.57	Rules:
14.14/4.57	lte(Cons(xs'), Cons(xs)) -> lte(xs', xs)
14.14/4.57	lte(Cons(xs), Nil) -> False
14.14/4.57	even(Cons(Nil)) -> False
14.14/4.57	even(Cons(Cons(xs))) -> even(xs)
14.14/4.57	notEmpty(Cons(xs)) -> True
14.14/4.57	notEmpty(Nil) -> False
14.14/4.57	lte(Nil, y) -> True
14.14/4.57	even(Nil) -> True
14.14/4.57	goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	and(False, False) -> False
14.14/4.57	and(True, False) -> False
14.14/4.57	and(False, True) -> False
14.14/4.57	and(True, True) -> True
14.14/4.57	
14.14/4.57	Types:
14.14/4.57	lte :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	Cons :: Cons:Nil -> Cons:Nil
14.14/4.57	Nil :: Cons:Nil
14.14/4.57	False :: False:True
14.14/4.57	even :: Cons:Nil -> False:True
14.14/4.57	notEmpty :: Cons:Nil -> False:True
14.14/4.57	True :: False:True
14.14/4.57	goal :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	and :: False:True -> False:True -> False:True
14.14/4.57	hole_False:True1_0 :: False:True
14.14/4.57	hole_Cons:Nil2_0 :: Cons:Nil
14.14/4.57	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
14.14/4.57	
14.14/4.57	
14.14/4.57	Generator Equations:
14.14/4.57	gen_Cons:Nil3_0(0) <=> Nil
14.14/4.57	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
14.14/4.57	
14.14/4.57	
14.14/4.57	The following defined symbols remain to be analysed:
14.14/4.57	lte, even
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(30) LowerBoundPropagationProof (FINISHED)
14.14/4.57	Propagated lower bound.
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(31)
14.14/4.57	BOUNDS(n^1, INF)
14.14/4.57	
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(32)
14.14/4.57	Obligation:
14.14/4.57	Innermost TRS:
14.14/4.57	Rules:
14.14/4.57	lte(Cons(xs'), Cons(xs)) -> lte(xs', xs)
14.14/4.57	lte(Cons(xs), Nil) -> False
14.14/4.57	even(Cons(Nil)) -> False
14.14/4.57	even(Cons(Cons(xs))) -> even(xs)
14.14/4.57	notEmpty(Cons(xs)) -> True
14.14/4.57	notEmpty(Nil) -> False
14.14/4.57	lte(Nil, y) -> True
14.14/4.57	even(Nil) -> True
14.14/4.57	goal(x, y) -> and(lte(x, y), even(x))
14.14/4.57	and(False, False) -> False
14.14/4.57	and(True, False) -> False
14.14/4.57	and(False, True) -> False
14.14/4.57	and(True, True) -> True
14.14/4.57	
14.14/4.57	Types:
14.14/4.57	lte :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	Cons :: Cons:Nil -> Cons:Nil
14.14/4.57	Nil :: Cons:Nil
14.14/4.57	False :: False:True
14.14/4.57	even :: Cons:Nil -> False:True
14.14/4.57	notEmpty :: Cons:Nil -> False:True
14.14/4.57	True :: False:True
14.14/4.57	goal :: Cons:Nil -> Cons:Nil -> False:True
14.14/4.57	and :: False:True -> False:True -> False:True
14.14/4.57	hole_False:True1_0 :: False:True
14.14/4.57	hole_Cons:Nil2_0 :: Cons:Nil
14.14/4.57	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
14.14/4.57	
14.14/4.57	
14.14/4.57	Lemmas:
14.14/4.57	lte(gen_Cons:Nil3_0(+(1, n5_0)), gen_Cons:Nil3_0(n5_0)) -> False, rt in Omega(1 + n5_0)
14.14/4.57	
14.14/4.57	
14.14/4.57	Generator Equations:
14.14/4.57	gen_Cons:Nil3_0(0) <=> Nil
14.14/4.57	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
14.14/4.57	
14.14/4.57	
14.14/4.57	The following defined symbols remain to be analysed:
14.14/4.57	even
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(33) RewriteLemmaProof (LOWER BOUND(ID))
14.14/4.57	Proved the following rewrite lemma:
14.14/4.57	even(gen_Cons:Nil3_0(+(1, *(2, n234_0)))) -> False, rt in Omega(1 + n234_0)
14.14/4.57	
14.14/4.57	Induction Base:
14.14/4.57	even(gen_Cons:Nil3_0(+(1, *(2, 0)))) ->_R^Omega(1)
14.14/4.57	False
14.14/4.57	
14.14/4.57	Induction Step:
14.14/4.57	even(gen_Cons:Nil3_0(+(1, *(2, +(n234_0, 1))))) ->_R^Omega(1)
14.14/4.57	even(gen_Cons:Nil3_0(+(1, *(2, n234_0)))) ->_IH
14.14/4.57	False
14.14/4.57	
14.14/4.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
14.14/4.57	----------------------------------------
14.14/4.57	
14.14/4.57	(34)
14.14/4.57	BOUNDS(1, INF)
14.14/4.59	EOF