15.44/5.11	WORST_CASE(Omega(n^1), O(n^1))
15.44/5.12	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
15.44/5.12	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
15.44/5.12	
15.44/5.12	
15.44/5.12	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
15.44/5.12	
15.44/5.12	(0) CpxTRS
15.44/5.12	(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
15.44/5.12	(2) CpxTRS
15.44/5.12	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
15.44/5.12	    (4) CpxTRS
15.44/5.12	    (5) CpxTrsMatchBoundsProof [FINISHED, 0 ms]
15.44/5.12	    (6) BOUNDS(1, n^1)
15.44/5.12	(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
15.44/5.12	(8) CpxTRS
15.44/5.12	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
15.44/5.12	    (10) typed CpxTrs
15.44/5.12	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
15.44/5.12	    (12) typed CpxTrs
15.44/5.12	    (13) RewriteLemmaProof [LOWER BOUND(ID), 271 ms]
15.44/5.12	    (14) BEST
15.44/5.12	        (15) proven lower bound
15.44/5.12	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
15.44/5.12	            (17) BOUNDS(n^1, INF)
15.44/5.12	        (18) typed CpxTrs
15.44/5.12	
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(0)
15.44/5.12	Obligation:
15.44/5.12	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
15.44/5.12	
15.44/5.12	
15.44/5.12	The TRS R consists of the following rules:
15.44/5.12	
15.44/5.12	   f(g(x), s(0), y) -> f(y, y, g(x))
15.44/5.12	   g(s(x)) -> s(g(x))
15.44/5.12	   g(0) -> 0
15.44/5.12	
15.44/5.12	S is empty.
15.44/5.12	Rewrite Strategy: FULL
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(1) DependencyGraphProof (UPPER BOUND(ID))
15.44/5.12	The following rules are not reachable from basic terms in the dependency graph and can be removed:
15.44/5.12	
15.44/5.12	f(g(x), s(0), y) -> f(y, y, g(x))
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(2)
15.44/5.12	Obligation:
15.44/5.12	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
15.44/5.12	
15.44/5.12	
15.44/5.12	The TRS R consists of the following rules:
15.44/5.12	
15.44/5.12	   g(s(x)) -> s(g(x))
15.44/5.12	   g(0) -> 0
15.44/5.12	
15.44/5.12	S is empty.
15.44/5.12	Rewrite Strategy: FULL
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(3) RelTrsToTrsProof (UPPER BOUND(ID))
15.44/5.12	transformed relative TRS to TRS
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(4)
15.44/5.12	Obligation:
15.44/5.12	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
15.44/5.12	
15.44/5.12	
15.44/5.12	The TRS R consists of the following rules:
15.44/5.12	
15.44/5.12	   g(s(x)) -> s(g(x))
15.44/5.12	   g(0) -> 0
15.44/5.12	
15.44/5.12	S is empty.
15.44/5.12	Rewrite Strategy: FULL
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(5) CpxTrsMatchBoundsProof (FINISHED)
15.44/5.12	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. 
15.44/5.12	The certificate found is represented by the following graph.
15.44/5.12	
15.44/5.12	"[5, 6, 7]
15.44/5.12	{(5,6,[g_1|0, 0|1]), (5,7,[s_1|1]), (6,6,[s_1|0, 0|0]), (7,6,[g_1|1, 0|1]), (7,7,[s_1|1])}"
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(6)
15.44/5.12	BOUNDS(1, n^1)
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(7) RenamingProof (BOTH BOUNDS(ID, ID))
15.44/5.12	Renamed function symbols to avoid clashes with predefined symbol.
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(8)
15.44/5.12	Obligation:
15.44/5.12	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
15.44/5.12	
15.44/5.12	
15.44/5.12	The TRS R consists of the following rules:
15.44/5.12	
15.44/5.12	   f(g(x), s(0'), y) -> f(y, y, g(x))
15.44/5.12	   g(s(x)) -> s(g(x))
15.44/5.12	   g(0') -> 0'
15.44/5.12	
15.44/5.12	S is empty.
15.44/5.12	Rewrite Strategy: FULL
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
15.44/5.12	Infered types.
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(10)
15.44/5.12	Obligation:
15.44/5.12	TRS:
15.44/5.12	Rules:
15.44/5.12	f(g(x), s(0'), y) -> f(y, y, g(x))
15.44/5.12	g(s(x)) -> s(g(x))
15.44/5.12	g(0') -> 0'
15.44/5.12	
15.44/5.12	Types:
15.44/5.12	f :: 0':s -> 0':s -> 0':s -> f
15.44/5.12	g :: 0':s -> 0':s
15.44/5.12	s :: 0':s -> 0':s
15.44/5.12	0' :: 0':s
15.44/5.12	hole_f1_0 :: f
15.44/5.12	hole_0':s2_0 :: 0':s
15.44/5.12	gen_0':s3_0 :: Nat -> 0':s
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(11) OrderProof (LOWER BOUND(ID))
15.44/5.12	Heuristically decided to analyse the following defined symbols:
15.44/5.12	f, g
15.44/5.12	
15.44/5.12	They will be analysed ascendingly in the following order:
15.44/5.12	g < f
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(12)
15.44/5.12	Obligation:
15.44/5.12	TRS:
15.44/5.12	Rules:
15.44/5.12	f(g(x), s(0'), y) -> f(y, y, g(x))
15.44/5.12	g(s(x)) -> s(g(x))
15.44/5.12	g(0') -> 0'
15.44/5.12	
15.44/5.12	Types:
15.44/5.12	f :: 0':s -> 0':s -> 0':s -> f
15.44/5.12	g :: 0':s -> 0':s
15.44/5.12	s :: 0':s -> 0':s
15.44/5.12	0' :: 0':s
15.44/5.12	hole_f1_0 :: f
15.44/5.12	hole_0':s2_0 :: 0':s
15.44/5.12	gen_0':s3_0 :: Nat -> 0':s
15.44/5.12	
15.44/5.12	
15.44/5.12	Generator Equations:
15.44/5.12	gen_0':s3_0(0) <=> 0'
15.44/5.12	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
15.44/5.12	
15.44/5.12	
15.44/5.12	The following defined symbols remain to be analysed:
15.44/5.12	g, f
15.44/5.12	
15.44/5.12	They will be analysed ascendingly in the following order:
15.44/5.12	g < f
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(13) RewriteLemmaProof (LOWER BOUND(ID))
15.44/5.12	Proved the following rewrite lemma:
15.44/5.12	g(gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
15.44/5.12	
15.44/5.12	Induction Base:
15.44/5.12	g(gen_0':s3_0(0)) ->_R^Omega(1)
15.44/5.12	0'
15.44/5.12	
15.44/5.12	Induction Step:
15.44/5.12	g(gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1)
15.44/5.12	s(g(gen_0':s3_0(n5_0))) ->_IH
15.44/5.12	s(gen_0':s3_0(c6_0))
15.44/5.12	
15.44/5.12	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(14)
15.44/5.12	Complex Obligation (BEST)
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(15)
15.44/5.12	Obligation:
15.44/5.12	Proved the lower bound n^1 for the following obligation:
15.44/5.12	
15.44/5.12	TRS:
15.44/5.12	Rules:
15.44/5.12	f(g(x), s(0'), y) -> f(y, y, g(x))
15.44/5.12	g(s(x)) -> s(g(x))
15.44/5.12	g(0') -> 0'
15.44/5.12	
15.44/5.12	Types:
15.44/5.12	f :: 0':s -> 0':s -> 0':s -> f
15.44/5.12	g :: 0':s -> 0':s
15.44/5.12	s :: 0':s -> 0':s
15.44/5.12	0' :: 0':s
15.44/5.12	hole_f1_0 :: f
15.44/5.12	hole_0':s2_0 :: 0':s
15.44/5.12	gen_0':s3_0 :: Nat -> 0':s
15.44/5.12	
15.44/5.12	
15.44/5.12	Generator Equations:
15.44/5.12	gen_0':s3_0(0) <=> 0'
15.44/5.12	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
15.44/5.12	
15.44/5.12	
15.44/5.12	The following defined symbols remain to be analysed:
15.44/5.12	g, f
15.44/5.12	
15.44/5.12	They will be analysed ascendingly in the following order:
15.44/5.12	g < f
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(16) LowerBoundPropagationProof (FINISHED)
15.44/5.12	Propagated lower bound.
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(17)
15.44/5.12	BOUNDS(n^1, INF)
15.44/5.12	
15.44/5.12	----------------------------------------
15.44/5.12	
15.44/5.12	(18)
15.44/5.12	Obligation:
15.44/5.12	TRS:
15.44/5.12	Rules:
15.44/5.12	f(g(x), s(0'), y) -> f(y, y, g(x))
15.44/5.12	g(s(x)) -> s(g(x))
15.44/5.12	g(0') -> 0'
15.44/5.12	
15.44/5.12	Types:
15.44/5.12	f :: 0':s -> 0':s -> 0':s -> f
15.44/5.12	g :: 0':s -> 0':s
15.44/5.12	s :: 0':s -> 0':s
15.44/5.12	0' :: 0':s
15.44/5.12	hole_f1_0 :: f
15.44/5.12	hole_0':s2_0 :: 0':s
15.44/5.12	gen_0':s3_0 :: Nat -> 0':s
15.44/5.12	
15.44/5.12	
15.44/5.12	Lemmas:
15.44/5.12	g(gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
15.44/5.12	
15.44/5.12	
15.44/5.12	Generator Equations:
15.44/5.12	gen_0':s3_0(0) <=> 0'
15.44/5.12	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
15.44/5.12	
15.44/5.12	
15.44/5.12	The following defined symbols remain to be analysed:
15.44/5.12	f
15.56/5.15	EOF