335.63/291.49	WORST_CASE(Omega(n^1), ?)
335.63/291.50	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
335.63/291.50	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
335.63/291.50	
335.63/291.50	
335.63/291.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
335.63/291.50	
335.63/291.50	(0) CpxTRS
335.63/291.50	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
335.63/291.50	(2) CpxTRS
335.63/291.50	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
335.63/291.50	(4) typed CpxTrs
335.63/291.50	(5) OrderProof [LOWER BOUND(ID), 0 ms]
335.63/291.50	(6) typed CpxTrs
335.63/291.50	(7) RewriteLemmaProof [LOWER BOUND(ID), 276 ms]
335.63/291.50	(8) BEST
335.63/291.50	    (9) proven lower bound
335.63/291.50	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
335.63/291.50	        (11) BOUNDS(n^1, INF)
335.63/291.50	    (12) typed CpxTrs
335.63/291.50	
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(0)
335.63/291.50	Obligation:
335.63/291.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
335.63/291.50	
335.63/291.50	
335.63/291.50	The TRS R consists of the following rules:
335.63/291.50	
335.63/291.50	   f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	   f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	   g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	   g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	   g(c(x, x)) -> f(x)
335.63/291.50	   id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	   id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	   id_inc(0) -> 0
335.63/291.50	   id_inc(0) -> s(0)
335.63/291.50	
335.63/291.50	S is empty.
335.63/291.50	Rewrite Strategy: FULL
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(1) RenamingProof (BOTH BOUNDS(ID, ID))
335.63/291.50	Renamed function symbols to avoid clashes with predefined symbol.
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(2)
335.63/291.50	Obligation:
335.63/291.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
335.63/291.50	
335.63/291.50	
335.63/291.50	The TRS R consists of the following rules:
335.63/291.50	
335.63/291.50	   f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	   f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	   g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	   g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	   g(c(x, x)) -> f(x)
335.63/291.50	   id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	   id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	   id_inc(0') -> 0'
335.63/291.50	   id_inc(0') -> s(0')
335.63/291.50	
335.63/291.50	S is empty.
335.63/291.50	Rewrite Strategy: FULL
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
335.63/291.50	Infered types.
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(4)
335.63/291.50	Obligation:
335.63/291.50	TRS:
335.63/291.50	Rules:
335.63/291.50	f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	g(c(x, x)) -> f(x)
335.63/291.50	id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	id_inc(0') -> 0'
335.63/291.50	id_inc(0') -> s(0')
335.63/291.50	
335.63/291.50	Types:
335.63/291.50	f :: s:c:0' -> f:g
335.63/291.50	s :: s:c:0' -> s:c:0'
335.63/291.50	id_inc :: s:c:0' -> s:c:0'
335.63/291.50	c :: s:c:0' -> s:c:0' -> s:c:0'
335.63/291.50	g :: s:c:0' -> f:g
335.63/291.50	0' :: s:c:0'
335.63/291.50	hole_f:g1_0 :: f:g
335.63/291.50	hole_s:c:0'2_0 :: s:c:0'
335.63/291.50	gen_s:c:0'3_0 :: Nat -> s:c:0'
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(5) OrderProof (LOWER BOUND(ID))
335.63/291.50	Heuristically decided to analyse the following defined symbols:
335.63/291.50	f, id_inc, g
335.63/291.50	
335.63/291.50	They will be analysed ascendingly in the following order:
335.63/291.50	id_inc < f
335.63/291.50	f = g
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(6)
335.63/291.50	Obligation:
335.63/291.50	TRS:
335.63/291.50	Rules:
335.63/291.50	f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	g(c(x, x)) -> f(x)
335.63/291.50	id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	id_inc(0') -> 0'
335.63/291.50	id_inc(0') -> s(0')
335.63/291.50	
335.63/291.50	Types:
335.63/291.50	f :: s:c:0' -> f:g
335.63/291.50	s :: s:c:0' -> s:c:0'
335.63/291.50	id_inc :: s:c:0' -> s:c:0'
335.63/291.50	c :: s:c:0' -> s:c:0' -> s:c:0'
335.63/291.50	g :: s:c:0' -> f:g
335.63/291.50	0' :: s:c:0'
335.63/291.50	hole_f:g1_0 :: f:g
335.63/291.50	hole_s:c:0'2_0 :: s:c:0'
335.63/291.50	gen_s:c:0'3_0 :: Nat -> s:c:0'
335.63/291.50	
335.63/291.50	
335.63/291.50	Generator Equations:
335.63/291.50	gen_s:c:0'3_0(0) <=> 0'
335.63/291.50	gen_s:c:0'3_0(+(x, 1)) <=> s(gen_s:c:0'3_0(x))
335.63/291.50	
335.63/291.50	
335.63/291.50	The following defined symbols remain to be analysed:
335.63/291.50	id_inc, f, g
335.63/291.50	
335.63/291.50	They will be analysed ascendingly in the following order:
335.63/291.50	id_inc < f
335.63/291.50	f = g
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(7) RewriteLemmaProof (LOWER BOUND(ID))
335.63/291.50	Proved the following rewrite lemma:
335.63/291.50	id_inc(gen_s:c:0'3_0(n5_0)) -> gen_s:c:0'3_0(n5_0), rt in Omega(1 + n5_0)
335.63/291.50	
335.63/291.50	Induction Base:
335.63/291.50	id_inc(gen_s:c:0'3_0(0)) ->_R^Omega(1)
335.63/291.50	0'
335.63/291.50	
335.63/291.50	Induction Step:
335.63/291.50	id_inc(gen_s:c:0'3_0(+(n5_0, 1))) ->_R^Omega(1)
335.63/291.50	s(id_inc(gen_s:c:0'3_0(n5_0))) ->_IH
335.63/291.50	s(gen_s:c:0'3_0(c6_0))
335.63/291.50	
335.63/291.50	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(8)
335.63/291.50	Complex Obligation (BEST)
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(9)
335.63/291.50	Obligation:
335.63/291.50	Proved the lower bound n^1 for the following obligation:
335.63/291.50	
335.63/291.50	TRS:
335.63/291.50	Rules:
335.63/291.50	f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	g(c(x, x)) -> f(x)
335.63/291.50	id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	id_inc(0') -> 0'
335.63/291.50	id_inc(0') -> s(0')
335.63/291.50	
335.63/291.50	Types:
335.63/291.50	f :: s:c:0' -> f:g
335.63/291.50	s :: s:c:0' -> s:c:0'
335.63/291.50	id_inc :: s:c:0' -> s:c:0'
335.63/291.50	c :: s:c:0' -> s:c:0' -> s:c:0'
335.63/291.50	g :: s:c:0' -> f:g
335.63/291.50	0' :: s:c:0'
335.63/291.50	hole_f:g1_0 :: f:g
335.63/291.50	hole_s:c:0'2_0 :: s:c:0'
335.63/291.50	gen_s:c:0'3_0 :: Nat -> s:c:0'
335.63/291.50	
335.63/291.50	
335.63/291.50	Generator Equations:
335.63/291.50	gen_s:c:0'3_0(0) <=> 0'
335.63/291.50	gen_s:c:0'3_0(+(x, 1)) <=> s(gen_s:c:0'3_0(x))
335.63/291.50	
335.63/291.50	
335.63/291.50	The following defined symbols remain to be analysed:
335.63/291.50	id_inc, f, g
335.63/291.50	
335.63/291.50	They will be analysed ascendingly in the following order:
335.63/291.50	id_inc < f
335.63/291.50	f = g
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(10) LowerBoundPropagationProof (FINISHED)
335.63/291.50	Propagated lower bound.
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(11)
335.63/291.50	BOUNDS(n^1, INF)
335.63/291.50	
335.63/291.50	----------------------------------------
335.63/291.50	
335.63/291.50	(12)
335.63/291.50	Obligation:
335.63/291.50	TRS:
335.63/291.50	Rules:
335.63/291.50	f(s(x)) -> f(id_inc(c(x, x)))
335.63/291.50	f(c(s(x), y)) -> g(c(x, y))
335.63/291.50	g(c(s(x), y)) -> g(c(y, x))
335.63/291.50	g(c(x, s(y))) -> g(c(y, x))
335.63/291.50	g(c(x, x)) -> f(x)
335.63/291.50	id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
335.63/291.50	id_inc(s(x)) -> s(id_inc(x))
335.63/291.50	id_inc(0') -> 0'
335.63/291.50	id_inc(0') -> s(0')
335.63/291.50	
335.63/291.50	Types:
335.63/291.50	f :: s:c:0' -> f:g
335.63/291.50	s :: s:c:0' -> s:c:0'
335.63/291.50	id_inc :: s:c:0' -> s:c:0'
335.63/291.50	c :: s:c:0' -> s:c:0' -> s:c:0'
335.63/291.50	g :: s:c:0' -> f:g
335.63/291.50	0' :: s:c:0'
335.63/291.50	hole_f:g1_0 :: f:g
335.63/291.50	hole_s:c:0'2_0 :: s:c:0'
335.63/291.50	gen_s:c:0'3_0 :: Nat -> s:c:0'
335.63/291.50	
335.63/291.50	
335.63/291.50	Lemmas:
335.63/291.50	id_inc(gen_s:c:0'3_0(n5_0)) -> gen_s:c:0'3_0(n5_0), rt in Omega(1 + n5_0)
335.63/291.50	
335.63/291.50	
335.63/291.50	Generator Equations:
335.63/291.50	gen_s:c:0'3_0(0) <=> 0'
335.63/291.50	gen_s:c:0'3_0(+(x, 1)) <=> s(gen_s:c:0'3_0(x))
335.63/291.50	
335.63/291.50	
335.63/291.50	The following defined symbols remain to be analysed:
335.63/291.50	g, f
335.63/291.50	
335.63/291.50	They will be analysed ascendingly in the following order:
335.63/291.50	f = g
369.44/300.11	EOF