316.28/291.50	WORST_CASE(Omega(n^1), ?)
316.28/291.51	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
316.28/291.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
316.28/291.51	
316.28/291.51	
316.28/291.51	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
316.28/291.51	
316.28/291.51	(0) CpxTRS
316.28/291.51	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
316.28/291.51	(2) CpxTRS
316.28/291.51	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
316.28/291.51	(4) typed CpxTrs
316.28/291.51	(5) OrderProof [LOWER BOUND(ID), 0 ms]
316.28/291.51	(6) typed CpxTrs
316.28/291.51	(7) RewriteLemmaProof [LOWER BOUND(ID), 958 ms]
316.28/291.51	(8) BEST
316.28/291.51	    (9) proven lower bound
316.28/291.51	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
316.28/291.51	        (11) BOUNDS(n^1, INF)
316.28/291.51	    (12) typed CpxTrs
316.28/291.51	        (13) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
316.28/291.51	        (14) BOUNDS(1, INF)
316.28/291.51	
316.28/291.51	
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(0)
316.28/291.51	Obligation:
316.28/291.51	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
316.28/291.51	
316.28/291.51	
316.28/291.51	The TRS R consists of the following rules:
316.28/291.51	
316.28/291.51	   fib(0) -> 0
316.28/291.51	   fib(s(0)) -> s(0)
316.28/291.51	   fib(s(s(0))) -> s(0)
316.28/291.51	   fib(s(s(x))) -> sp(g(x))
316.28/291.51	   g(0) -> pair(s(0), 0)
316.28/291.51	   g(s(0)) -> pair(s(0), s(0))
316.28/291.51	   g(s(x)) -> np(g(x))
316.28/291.51	   sp(pair(x, y)) -> +(x, y)
316.28/291.51	   np(pair(x, y)) -> pair(+(x, y), x)
316.28/291.51	   +(x, 0) -> x
316.28/291.51	   +(x, s(y)) -> s(+(x, y))
316.28/291.51	
316.28/291.51	S is empty.
316.28/291.51	Rewrite Strategy: FULL
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(1) RenamingProof (BOTH BOUNDS(ID, ID))
316.28/291.51	Renamed function symbols to avoid clashes with predefined symbol.
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(2)
316.28/291.51	Obligation:
316.28/291.51	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
316.28/291.51	
316.28/291.51	
316.28/291.51	The TRS R consists of the following rules:
316.28/291.51	
316.28/291.51	   fib(0') -> 0'
316.28/291.51	   fib(s(0')) -> s(0')
316.28/291.51	   fib(s(s(0'))) -> s(0')
316.28/291.51	   fib(s(s(x))) -> sp(g(x))
316.28/291.51	   g(0') -> pair(s(0'), 0')
316.28/291.51	   g(s(0')) -> pair(s(0'), s(0'))
316.28/291.51	   g(s(x)) -> np(g(x))
316.28/291.51	   sp(pair(x, y)) -> +'(x, y)
316.28/291.51	   np(pair(x, y)) -> pair(+'(x, y), x)
316.28/291.51	   +'(x, 0') -> x
316.28/291.51	   +'(x, s(y)) -> s(+'(x, y))
316.28/291.51	
316.28/291.51	S is empty.
316.28/291.51	Rewrite Strategy: FULL
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
316.28/291.51	Infered types.
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(4)
316.28/291.51	Obligation:
316.28/291.51	TRS:
316.28/291.51	Rules:
316.28/291.51	fib(0') -> 0'
316.28/291.51	fib(s(0')) -> s(0')
316.28/291.51	fib(s(s(0'))) -> s(0')
316.28/291.51	fib(s(s(x))) -> sp(g(x))
316.28/291.51	g(0') -> pair(s(0'), 0')
316.28/291.51	g(s(0')) -> pair(s(0'), s(0'))
316.28/291.51	g(s(x)) -> np(g(x))
316.28/291.51	sp(pair(x, y)) -> +'(x, y)
316.28/291.51	np(pair(x, y)) -> pair(+'(x, y), x)
316.28/291.51	+'(x, 0') -> x
316.28/291.51	+'(x, s(y)) -> s(+'(x, y))
316.28/291.51	
316.28/291.51	Types:
316.28/291.51	fib :: 0':s -> 0':s
316.28/291.51	0' :: 0':s
316.28/291.51	s :: 0':s -> 0':s
316.28/291.51	sp :: pair -> 0':s
316.28/291.51	g :: 0':s -> pair
316.28/291.51	pair :: 0':s -> 0':s -> pair
316.28/291.51	np :: pair -> pair
316.28/291.51	+' :: 0':s -> 0':s -> 0':s
316.28/291.51	hole_0':s1_0 :: 0':s
316.28/291.51	hole_pair2_0 :: pair
316.28/291.51	gen_0':s3_0 :: Nat -> 0':s
316.28/291.51	
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(5) OrderProof (LOWER BOUND(ID))
316.28/291.51	Heuristically decided to analyse the following defined symbols:
316.28/291.51	g, +'
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(6)
316.28/291.51	Obligation:
316.28/291.51	TRS:
316.28/291.51	Rules:
316.28/291.51	fib(0') -> 0'
316.28/291.51	fib(s(0')) -> s(0')
316.28/291.51	fib(s(s(0'))) -> s(0')
316.28/291.51	fib(s(s(x))) -> sp(g(x))
316.28/291.51	g(0') -> pair(s(0'), 0')
316.28/291.51	g(s(0')) -> pair(s(0'), s(0'))
316.28/291.51	g(s(x)) -> np(g(x))
316.28/291.51	sp(pair(x, y)) -> +'(x, y)
316.28/291.51	np(pair(x, y)) -> pair(+'(x, y), x)
316.28/291.51	+'(x, 0') -> x
316.28/291.51	+'(x, s(y)) -> s(+'(x, y))
316.28/291.51	
316.28/291.51	Types:
316.28/291.51	fib :: 0':s -> 0':s
316.28/291.51	0' :: 0':s
316.28/291.51	s :: 0':s -> 0':s
316.28/291.51	sp :: pair -> 0':s
316.28/291.51	g :: 0':s -> pair
316.28/291.51	pair :: 0':s -> 0':s -> pair
316.28/291.51	np :: pair -> pair
316.28/291.51	+' :: 0':s -> 0':s -> 0':s
316.28/291.51	hole_0':s1_0 :: 0':s
316.28/291.51	hole_pair2_0 :: pair
316.28/291.51	gen_0':s3_0 :: Nat -> 0':s
316.28/291.51	
316.28/291.51	
316.28/291.51	Generator Equations:
316.28/291.51	gen_0':s3_0(0) <=> 0'
316.28/291.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
316.28/291.51	
316.28/291.51	
316.28/291.51	The following defined symbols remain to be analysed:
316.28/291.51	g, +'
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(7) RewriteLemmaProof (LOWER BOUND(ID))
316.28/291.51	Proved the following rewrite lemma:
316.28/291.51	g(gen_0':s3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
316.28/291.51	
316.28/291.51	Induction Base:
316.28/291.51	g(gen_0':s3_0(+(1, 0)))
316.28/291.51	
316.28/291.51	Induction Step:
316.28/291.51	g(gen_0':s3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1)
316.28/291.51	np(g(gen_0':s3_0(+(1, n5_0)))) ->_IH
316.28/291.51	np(*4_0)
316.28/291.51	
316.28/291.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(8)
316.28/291.51	Complex Obligation (BEST)
316.28/291.51	
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(9)
316.28/291.51	Obligation:
316.28/291.51	Proved the lower bound n^1 for the following obligation:
316.28/291.51	
316.28/291.51	TRS:
316.28/291.51	Rules:
316.28/291.51	fib(0') -> 0'
316.28/291.51	fib(s(0')) -> s(0')
316.28/291.51	fib(s(s(0'))) -> s(0')
316.28/291.51	fib(s(s(x))) -> sp(g(x))
316.28/291.51	g(0') -> pair(s(0'), 0')
316.28/291.51	g(s(0')) -> pair(s(0'), s(0'))
316.28/291.51	g(s(x)) -> np(g(x))
316.28/291.51	sp(pair(x, y)) -> +'(x, y)
316.28/291.51	np(pair(x, y)) -> pair(+'(x, y), x)
316.28/291.51	+'(x, 0') -> x
316.28/291.51	+'(x, s(y)) -> s(+'(x, y))
316.28/291.51	
316.28/291.51	Types:
316.28/291.51	fib :: 0':s -> 0':s
316.28/291.51	0' :: 0':s
316.28/291.51	s :: 0':s -> 0':s
316.28/291.51	sp :: pair -> 0':s
316.28/291.51	g :: 0':s -> pair
316.28/291.51	pair :: 0':s -> 0':s -> pair
316.28/291.51	np :: pair -> pair
316.28/291.51	+' :: 0':s -> 0':s -> 0':s
316.28/291.51	hole_0':s1_0 :: 0':s
316.28/291.51	hole_pair2_0 :: pair
316.28/291.51	gen_0':s3_0 :: Nat -> 0':s
316.28/291.51	
316.28/291.51	
316.28/291.51	Generator Equations:
316.28/291.51	gen_0':s3_0(0) <=> 0'
316.28/291.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
316.28/291.51	
316.28/291.51	
316.28/291.51	The following defined symbols remain to be analysed:
316.28/291.51	g, +'
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(10) LowerBoundPropagationProof (FINISHED)
316.28/291.51	Propagated lower bound.
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(11)
316.28/291.51	BOUNDS(n^1, INF)
316.28/291.51	
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(12)
316.28/291.51	Obligation:
316.28/291.51	TRS:
316.28/291.51	Rules:
316.28/291.51	fib(0') -> 0'
316.28/291.51	fib(s(0')) -> s(0')
316.28/291.51	fib(s(s(0'))) -> s(0')
316.28/291.51	fib(s(s(x))) -> sp(g(x))
316.28/291.51	g(0') -> pair(s(0'), 0')
316.28/291.51	g(s(0')) -> pair(s(0'), s(0'))
316.28/291.51	g(s(x)) -> np(g(x))
316.28/291.51	sp(pair(x, y)) -> +'(x, y)
316.28/291.51	np(pair(x, y)) -> pair(+'(x, y), x)
316.28/291.51	+'(x, 0') -> x
316.28/291.51	+'(x, s(y)) -> s(+'(x, y))
316.28/291.51	
316.28/291.51	Types:
316.28/291.51	fib :: 0':s -> 0':s
316.28/291.51	0' :: 0':s
316.28/291.51	s :: 0':s -> 0':s
316.28/291.51	sp :: pair -> 0':s
316.28/291.51	g :: 0':s -> pair
316.28/291.51	pair :: 0':s -> 0':s -> pair
316.28/291.51	np :: pair -> pair
316.28/291.51	+' :: 0':s -> 0':s -> 0':s
316.28/291.51	hole_0':s1_0 :: 0':s
316.28/291.51	hole_pair2_0 :: pair
316.28/291.51	gen_0':s3_0 :: Nat -> 0':s
316.28/291.51	
316.28/291.51	
316.28/291.51	Lemmas:
316.28/291.51	g(gen_0':s3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
316.28/291.51	
316.28/291.51	
316.28/291.51	Generator Equations:
316.28/291.51	gen_0':s3_0(0) <=> 0'
316.28/291.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
316.28/291.51	
316.28/291.51	
316.28/291.51	The following defined symbols remain to be analysed:
316.28/291.51	+'
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(13) RewriteLemmaProof (LOWER BOUND(ID))
316.28/291.51	Proved the following rewrite lemma:
316.28/291.51	+'(gen_0':s3_0(a), gen_0':s3_0(n4858_0)) -> gen_0':s3_0(+(n4858_0, a)), rt in Omega(1 + n4858_0)
316.28/291.51	
316.28/291.51	Induction Base:
316.28/291.51	+'(gen_0':s3_0(a), gen_0':s3_0(0)) ->_R^Omega(1)
316.28/291.51	gen_0':s3_0(a)
316.28/291.51	
316.28/291.51	Induction Step:
316.28/291.51	+'(gen_0':s3_0(a), gen_0':s3_0(+(n4858_0, 1))) ->_R^Omega(1)
316.28/291.51	s(+'(gen_0':s3_0(a), gen_0':s3_0(n4858_0))) ->_IH
316.28/291.51	s(gen_0':s3_0(+(a, c4859_0)))
316.28/291.51	
316.28/291.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
316.28/291.51	----------------------------------------
316.28/291.51	
316.28/291.51	(14)
316.28/291.51	BOUNDS(1, INF)
316.36/291.54	EOF