11.45/3.99	WORST_CASE(Omega(n^1), O(n^1))
11.68/4.00	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
11.68/4.00	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.68/4.00	
11.68/4.00	
11.68/4.00	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
11.68/4.00	
11.68/4.00	(0) CpxTRS
11.68/4.00	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
11.68/4.00	(2) CdtProblem
11.68/4.00	    (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
11.68/4.00	    (4) CdtProblem
11.68/4.00	    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
11.68/4.00	    (6) CdtProblem
11.68/4.00	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 3 ms]
11.68/4.00	    (8) CdtProblem
11.68/4.00	    (9) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
11.68/4.00	    (10) BOUNDS(1, 1)
11.68/4.00	(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
11.68/4.00	(12) CpxTRS
11.68/4.00	    (13) SlicingProof [LOWER BOUND(ID), 0 ms]
11.68/4.00	    (14) CpxTRS
11.68/4.00	    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
11.68/4.00	    (16) typed CpxTrs
11.68/4.00	    (17) OrderProof [LOWER BOUND(ID), 0 ms]
11.68/4.00	    (18) typed CpxTrs
11.68/4.00	    (19) RewriteLemmaProof [LOWER BOUND(ID), 286 ms]
11.68/4.00	    (20) proven lower bound
11.68/4.00	    (21) LowerBoundPropagationProof [FINISHED, 0 ms]
11.68/4.00	    (22) BOUNDS(n^1, INF)
11.68/4.00	
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(0)
11.68/4.00	Obligation:
11.68/4.00	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
11.68/4.00	
11.68/4.00	
11.68/4.00	The TRS R consists of the following rules:
11.68/4.00	
11.68/4.00	   duplicate(Cons(x, xs)) -> Cons(x, Cons(x, duplicate(xs)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	S is empty.
11.68/4.00	Rewrite Strategy: INNERMOST
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
11.68/4.00	Converted Cpx (relative) TRS to CDT
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(2)
11.68/4.00	Obligation:
11.68/4.00	Complexity Dependency Tuples Problem
11.68/4.00	
11.68/4.00	Rules:
11.68/4.00	   duplicate(Cons(z0, z1)) -> Cons(z0, Cons(z0, duplicate(z1)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(z0) -> duplicate(z0)
11.68/4.00	Tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	   DUPLICATE(Nil) -> c1
11.68/4.00	   GOAL(z0) -> c2(DUPLICATE(z0))
11.68/4.00	S tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	   DUPLICATE(Nil) -> c1
11.68/4.00	   GOAL(z0) -> c2(DUPLICATE(z0))
11.68/4.00	K tuples:none
11.68/4.00	Defined Rule Symbols:   duplicate_1, goal_1
11.68/4.00	
11.68/4.00	Defined Pair Symbols:   DUPLICATE_1, GOAL_1
11.68/4.00	
11.68/4.00	Compound Symbols:   c_1, c1, c2_1
11.68/4.00	
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(3) CdtLeafRemovalProof (ComplexityIfPolyImplication)
11.68/4.00	Removed 1 leading nodes:
11.68/4.00	   GOAL(z0) -> c2(DUPLICATE(z0))
11.68/4.00	Removed 1 trailing nodes:
11.68/4.00	   DUPLICATE(Nil) -> c1
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(4)
11.68/4.00	Obligation:
11.68/4.00	Complexity Dependency Tuples Problem
11.68/4.00	
11.68/4.00	Rules:
11.68/4.00	   duplicate(Cons(z0, z1)) -> Cons(z0, Cons(z0, duplicate(z1)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(z0) -> duplicate(z0)
11.68/4.00	Tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	S tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	K tuples:none
11.68/4.00	Defined Rule Symbols:   duplicate_1, goal_1
11.68/4.00	
11.68/4.00	Defined Pair Symbols:   DUPLICATE_1
11.68/4.00	
11.68/4.00	Compound Symbols:   c_1
11.68/4.00	
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
11.68/4.00	The following rules are not usable and were removed:
11.68/4.00	   duplicate(Cons(z0, z1)) -> Cons(z0, Cons(z0, duplicate(z1)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(z0) -> duplicate(z0)
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(6)
11.68/4.00	Obligation:
11.68/4.00	Complexity Dependency Tuples Problem
11.68/4.00	
11.68/4.00	Rules:none
11.68/4.00	Tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	S tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	K tuples:none
11.68/4.00	Defined Rule Symbols:none
11.68/4.00	
11.68/4.00	Defined Pair Symbols:   DUPLICATE_1
11.68/4.00	
11.68/4.00	Compound Symbols:   c_1
11.68/4.00	
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
11.68/4.00	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	We considered the (Usable) Rules:none
11.68/4.00	And the Tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	The order we found is given by the following interpretation:
11.68/4.00	
11.68/4.00	Polynomial interpretation :
11.68/4.00	
11.68/4.00	   POL(Cons(x_1, x_2)) = [1] + x_2
11.68/4.00	   POL(DUPLICATE(x_1)) = x_1
11.68/4.00	   POL(c(x_1)) = x_1
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(8)
11.68/4.00	Obligation:
11.68/4.00	Complexity Dependency Tuples Problem
11.68/4.00	
11.68/4.00	Rules:none
11.68/4.00	Tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	S tuples:none
11.68/4.00	K tuples:
11.68/4.00	   DUPLICATE(Cons(z0, z1)) -> c(DUPLICATE(z1))
11.68/4.00	Defined Rule Symbols:none
11.68/4.00	
11.68/4.00	Defined Pair Symbols:   DUPLICATE_1
11.68/4.00	
11.68/4.00	Compound Symbols:   c_1
11.68/4.00	
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(9) SIsEmptyProof (BOTH BOUNDS(ID, ID))
11.68/4.00	The set S is empty
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(10)
11.68/4.00	BOUNDS(1, 1)
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(11) RenamingProof (BOTH BOUNDS(ID, ID))
11.68/4.00	Renamed function symbols to avoid clashes with predefined symbol.
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(12)
11.68/4.00	Obligation:
11.68/4.00	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
11.68/4.00	
11.68/4.00	
11.68/4.00	The TRS R consists of the following rules:
11.68/4.00	
11.68/4.00	   duplicate(Cons(x, xs)) -> Cons(x, Cons(x, duplicate(xs)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	S is empty.
11.68/4.00	Rewrite Strategy: INNERMOST
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(13) SlicingProof (LOWER BOUND(ID))
11.68/4.00	Sliced the following arguments:
11.68/4.00	Cons/0
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(14)
11.68/4.00	Obligation:
11.68/4.00	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
11.68/4.00	
11.68/4.00	
11.68/4.00	The TRS R consists of the following rules:
11.68/4.00	
11.68/4.00	   duplicate(Cons(xs)) -> Cons(Cons(duplicate(xs)))
11.68/4.00	   duplicate(Nil) -> Nil
11.68/4.00	   goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	S is empty.
11.68/4.00	Rewrite Strategy: INNERMOST
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
11.68/4.00	Infered types.
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(16)
11.68/4.00	Obligation:
11.68/4.00	Innermost TRS:
11.68/4.00	Rules:
11.68/4.00	duplicate(Cons(xs)) -> Cons(Cons(duplicate(xs)))
11.68/4.00	duplicate(Nil) -> Nil
11.68/4.00	goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	Types:
11.68/4.00	duplicate :: Cons:Nil -> Cons:Nil
11.68/4.00	Cons :: Cons:Nil -> Cons:Nil
11.68/4.00	Nil :: Cons:Nil
11.68/4.00	goal :: Cons:Nil -> Cons:Nil
11.68/4.00	hole_Cons:Nil1_0 :: Cons:Nil
11.68/4.00	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
11.68/4.00	
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(17) OrderProof (LOWER BOUND(ID))
11.68/4.00	Heuristically decided to analyse the following defined symbols:
11.68/4.00	duplicate
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(18)
11.68/4.00	Obligation:
11.68/4.00	Innermost TRS:
11.68/4.00	Rules:
11.68/4.00	duplicate(Cons(xs)) -> Cons(Cons(duplicate(xs)))
11.68/4.00	duplicate(Nil) -> Nil
11.68/4.00	goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	Types:
11.68/4.00	duplicate :: Cons:Nil -> Cons:Nil
11.68/4.00	Cons :: Cons:Nil -> Cons:Nil
11.68/4.00	Nil :: Cons:Nil
11.68/4.00	goal :: Cons:Nil -> Cons:Nil
11.68/4.00	hole_Cons:Nil1_0 :: Cons:Nil
11.68/4.00	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
11.68/4.00	
11.68/4.00	
11.68/4.00	Generator Equations:
11.68/4.00	gen_Cons:Nil2_0(0) <=> Nil
11.68/4.00	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
11.68/4.00	
11.68/4.00	
11.68/4.00	The following defined symbols remain to be analysed:
11.68/4.00	duplicate
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(19) RewriteLemmaProof (LOWER BOUND(ID))
11.68/4.00	Proved the following rewrite lemma:
11.68/4.00	duplicate(gen_Cons:Nil2_0(n4_0)) -> gen_Cons:Nil2_0(*(2, n4_0)), rt in Omega(1 + n4_0)
11.68/4.00	
11.68/4.00	Induction Base:
11.68/4.00	duplicate(gen_Cons:Nil2_0(0)) ->_R^Omega(1)
11.68/4.00	Nil
11.68/4.00	
11.68/4.00	Induction Step:
11.68/4.00	duplicate(gen_Cons:Nil2_0(+(n4_0, 1))) ->_R^Omega(1)
11.68/4.00	Cons(Cons(duplicate(gen_Cons:Nil2_0(n4_0)))) ->_IH
11.68/4.00	Cons(Cons(gen_Cons:Nil2_0(*(2, c5_0))))
11.68/4.00	
11.68/4.00	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(20)
11.68/4.00	Obligation:
11.68/4.00	Proved the lower bound n^1 for the following obligation:
11.68/4.00	
11.68/4.00	Innermost TRS:
11.68/4.00	Rules:
11.68/4.00	duplicate(Cons(xs)) -> Cons(Cons(duplicate(xs)))
11.68/4.00	duplicate(Nil) -> Nil
11.68/4.00	goal(x) -> duplicate(x)
11.68/4.00	
11.68/4.00	Types:
11.68/4.00	duplicate :: Cons:Nil -> Cons:Nil
11.68/4.00	Cons :: Cons:Nil -> Cons:Nil
11.68/4.00	Nil :: Cons:Nil
11.68/4.00	goal :: Cons:Nil -> Cons:Nil
11.68/4.00	hole_Cons:Nil1_0 :: Cons:Nil
11.68/4.00	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
11.68/4.00	
11.68/4.00	
11.68/4.00	Generator Equations:
11.68/4.00	gen_Cons:Nil2_0(0) <=> Nil
11.68/4.00	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
11.68/4.00	
11.68/4.00	
11.68/4.00	The following defined symbols remain to be analysed:
11.68/4.00	duplicate
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(21) LowerBoundPropagationProof (FINISHED)
11.68/4.00	Propagated lower bound.
11.68/4.00	----------------------------------------
11.68/4.00	
11.68/4.00	(22)
11.68/4.00	BOUNDS(n^1, INF)
11.68/4.04	EOF