302.47/291.47	WORST_CASE(Omega(n^1), ?)
302.47/291.47	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
302.47/291.47	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
302.47/291.47	
302.47/291.47	
302.47/291.47	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
302.47/291.47	
302.47/291.47	(0) CpxTRS
302.47/291.47	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
302.47/291.47	(2) CpxTRS
302.47/291.47	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
302.47/291.47	(4) typed CpxTrs
302.47/291.47	(5) OrderProof [LOWER BOUND(ID), 0 ms]
302.47/291.47	(6) typed CpxTrs
302.47/291.47	(7) RewriteLemmaProof [LOWER BOUND(ID), 428 ms]
302.47/291.47	(8) BEST
302.47/291.47	    (9) proven lower bound
302.47/291.47	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
302.47/291.47	        (11) BOUNDS(n^1, INF)
302.47/291.47	    (12) typed CpxTrs
302.47/291.47	
302.47/291.47	
302.47/291.47	----------------------------------------
302.47/291.47	
302.47/291.47	(0)
302.47/291.47	Obligation:
302.47/291.47	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
302.47/291.47	
302.47/291.47	
302.47/291.47	The TRS R consists of the following rules:
302.47/291.47	
302.47/291.47	   f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.47	   select(cons(ap, xs)) -> ap
302.47/291.47	   select(cons(ap, xs)) -> select(xs)
302.47/291.47	   addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.47	
302.47/291.47	S is empty.
302.47/291.47	Rewrite Strategy: FULL
302.47/291.47	----------------------------------------
302.47/291.47	
302.47/291.47	(1) RenamingProof (BOTH BOUNDS(ID, ID))
302.47/291.47	Renamed function symbols to avoid clashes with predefined symbol.
302.47/291.47	----------------------------------------
302.47/291.47	
302.47/291.47	(2)
302.47/291.47	Obligation:
302.47/291.47	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
302.47/291.47	
302.47/291.47	
302.47/291.47	The TRS R consists of the following rules:
302.47/291.47	
302.47/291.47	   f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.47	   select(cons(ap, xs)) -> ap
302.47/291.47	   select(cons(ap, xs)) -> select(xs)
302.47/291.47	   addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.47	
302.47/291.47	S is empty.
302.47/291.47	Rewrite Strategy: FULL
302.47/291.47	----------------------------------------
302.47/291.47	
302.47/291.47	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
302.47/291.47	Infered types.
302.47/291.47	----------------------------------------
302.47/291.47	
302.47/291.47	(4)
302.47/291.47	Obligation:
302.47/291.47	TRS:
302.47/291.47	Rules:
302.47/291.47	f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.47	select(cons(ap, xs)) -> ap
302.47/291.47	select(cons(ap, xs)) -> select(xs)
302.47/291.47	addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.47	
302.47/291.47	Types:
302.47/291.47	f :: node -> f
302.47/291.47	node :: s -> cons -> node
302.47/291.48	s :: s -> s
302.47/291.48	addchild :: node -> node -> node
302.47/291.48	select :: cons -> node
302.47/291.48	cons :: node -> cons -> cons
302.47/291.48	hole_f1_0 :: f
302.47/291.48	hole_node2_0 :: node
302.47/291.48	hole_s3_0 :: s
302.47/291.48	hole_cons4_0 :: cons
302.47/291.48	gen_s5_0 :: Nat -> s
302.47/291.48	gen_cons6_0 :: Nat -> cons
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(5) OrderProof (LOWER BOUND(ID))
302.47/291.48	Heuristically decided to analyse the following defined symbols:
302.47/291.48	f, select
302.47/291.48	
302.47/291.48	They will be analysed ascendingly in the following order:
302.47/291.48	select < f
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(6)
302.47/291.48	Obligation:
302.47/291.48	TRS:
302.47/291.48	Rules:
302.47/291.48	f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.48	select(cons(ap, xs)) -> ap
302.47/291.48	select(cons(ap, xs)) -> select(xs)
302.47/291.48	addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.48	
302.47/291.48	Types:
302.47/291.48	f :: node -> f
302.47/291.48	node :: s -> cons -> node
302.47/291.48	s :: s -> s
302.47/291.48	addchild :: node -> node -> node
302.47/291.48	select :: cons -> node
302.47/291.48	cons :: node -> cons -> cons
302.47/291.48	hole_f1_0 :: f
302.47/291.48	hole_node2_0 :: node
302.47/291.48	hole_s3_0 :: s
302.47/291.48	hole_cons4_0 :: cons
302.47/291.48	gen_s5_0 :: Nat -> s
302.47/291.48	gen_cons6_0 :: Nat -> cons
302.47/291.48	
302.47/291.48	
302.47/291.48	Generator Equations:
302.47/291.48	gen_s5_0(0) <=> hole_s3_0
302.47/291.48	gen_s5_0(+(x, 1)) <=> s(gen_s5_0(x))
302.47/291.48	gen_cons6_0(0) <=> hole_cons4_0
302.47/291.48	gen_cons6_0(+(x, 1)) <=> cons(node(hole_s3_0, hole_cons4_0), gen_cons6_0(x))
302.47/291.48	
302.47/291.48	
302.47/291.48	The following defined symbols remain to be analysed:
302.47/291.48	select, f
302.47/291.48	
302.47/291.48	They will be analysed ascendingly in the following order:
302.47/291.48	select < f
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(7) RewriteLemmaProof (LOWER BOUND(ID))
302.47/291.48	Proved the following rewrite lemma:
302.47/291.48	select(gen_cons6_0(+(1, n8_0))) -> *7_0, rt in Omega(n8_0)
302.47/291.48	
302.47/291.48	Induction Base:
302.47/291.48	select(gen_cons6_0(+(1, 0)))
302.47/291.48	
302.47/291.48	Induction Step:
302.47/291.48	select(gen_cons6_0(+(1, +(n8_0, 1)))) ->_R^Omega(1)
302.47/291.48	select(gen_cons6_0(+(1, n8_0))) ->_IH
302.47/291.48	*7_0
302.47/291.48	
302.47/291.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(8)
302.47/291.48	Complex Obligation (BEST)
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(9)
302.47/291.48	Obligation:
302.47/291.48	Proved the lower bound n^1 for the following obligation:
302.47/291.48	
302.47/291.48	TRS:
302.47/291.48	Rules:
302.47/291.48	f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.48	select(cons(ap, xs)) -> ap
302.47/291.48	select(cons(ap, xs)) -> select(xs)
302.47/291.48	addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.48	
302.47/291.48	Types:
302.47/291.48	f :: node -> f
302.47/291.48	node :: s -> cons -> node
302.47/291.48	s :: s -> s
302.47/291.48	addchild :: node -> node -> node
302.47/291.48	select :: cons -> node
302.47/291.48	cons :: node -> cons -> cons
302.47/291.48	hole_f1_0 :: f
302.47/291.48	hole_node2_0 :: node
302.47/291.48	hole_s3_0 :: s
302.47/291.48	hole_cons4_0 :: cons
302.47/291.48	gen_s5_0 :: Nat -> s
302.47/291.48	gen_cons6_0 :: Nat -> cons
302.47/291.48	
302.47/291.48	
302.47/291.48	Generator Equations:
302.47/291.48	gen_s5_0(0) <=> hole_s3_0
302.47/291.48	gen_s5_0(+(x, 1)) <=> s(gen_s5_0(x))
302.47/291.48	gen_cons6_0(0) <=> hole_cons4_0
302.47/291.48	gen_cons6_0(+(x, 1)) <=> cons(node(hole_s3_0, hole_cons4_0), gen_cons6_0(x))
302.47/291.48	
302.47/291.48	
302.47/291.48	The following defined symbols remain to be analysed:
302.47/291.48	select, f
302.47/291.48	
302.47/291.48	They will be analysed ascendingly in the following order:
302.47/291.48	select < f
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(10) LowerBoundPropagationProof (FINISHED)
302.47/291.48	Propagated lower bound.
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(11)
302.47/291.48	BOUNDS(n^1, INF)
302.47/291.48	
302.47/291.48	----------------------------------------
302.47/291.48	
302.47/291.48	(12)
302.47/291.48	Obligation:
302.47/291.48	TRS:
302.47/291.48	Rules:
302.47/291.48	f(node(s(n), xs)) -> f(addchild(select(xs), node(n, xs)))
302.47/291.48	select(cons(ap, xs)) -> ap
302.47/291.48	select(cons(ap, xs)) -> select(xs)
302.47/291.48	addchild(node(y, ys), node(n, xs)) -> node(y, cons(node(n, xs), ys))
302.47/291.48	
302.47/291.48	Types:
302.47/291.48	f :: node -> f
302.47/291.48	node :: s -> cons -> node
302.47/291.48	s :: s -> s
302.47/291.48	addchild :: node -> node -> node
302.47/291.48	select :: cons -> node
302.47/291.48	cons :: node -> cons -> cons
302.47/291.48	hole_f1_0 :: f
302.47/291.48	hole_node2_0 :: node
302.47/291.48	hole_s3_0 :: s
302.47/291.48	hole_cons4_0 :: cons
302.47/291.48	gen_s5_0 :: Nat -> s
302.47/291.48	gen_cons6_0 :: Nat -> cons
302.47/291.48	
302.47/291.48	
302.47/291.48	Lemmas:
302.47/291.48	select(gen_cons6_0(+(1, n8_0))) -> *7_0, rt in Omega(n8_0)
302.47/291.48	
302.47/291.48	
302.47/291.48	Generator Equations:
302.47/291.48	gen_s5_0(0) <=> hole_s3_0
302.47/291.48	gen_s5_0(+(x, 1)) <=> s(gen_s5_0(x))
302.47/291.48	gen_cons6_0(0) <=> hole_cons4_0
302.47/291.48	gen_cons6_0(+(x, 1)) <=> cons(node(hole_s3_0, hole_cons4_0), gen_cons6_0(x))
302.47/291.48	
302.47/291.48	
302.47/291.48	The following defined symbols remain to be analysed:
302.47/291.48	f
302.51/291.51	EOF