11.62/3.78	WORST_CASE(Omega(n^1), O(n^1))
11.62/3.78	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
11.62/3.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.62/3.78	
11.62/3.78	
11.62/3.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
11.62/3.78	
11.62/3.78	(0) CpxTRS
11.62/3.78	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
11.62/3.78	(2) CpxTRS
11.62/3.78	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms]
11.62/3.78	    (4) BOUNDS(1, n^1)
11.62/3.78	(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
11.62/3.78	(6) CpxTRS
11.62/3.78	    (7) SlicingProof [LOWER BOUND(ID), 0 ms]
11.62/3.78	    (8) CpxTRS
11.62/3.78	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
11.62/3.78	    (10) typed CpxTrs
11.62/3.78	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
11.62/3.78	    (12) typed CpxTrs
11.62/3.78	    (13) RewriteLemmaProof [LOWER BOUND(ID), 487 ms]
11.62/3.78	    (14) BEST
11.62/3.78	        (15) proven lower bound
11.62/3.78	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
11.62/3.78	            (17) BOUNDS(n^1, INF)
11.62/3.78	        (18) typed CpxTrs
11.62/3.78	            (19) RewriteLemmaProof [LOWER BOUND(ID), 93 ms]
11.62/3.78	            (20) typed CpxTrs
11.62/3.78	            (21) RewriteLemmaProof [LOWER BOUND(ID), 46 ms]
11.62/3.78	            (22) BOUNDS(1, INF)
11.62/3.78	
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(0)
11.62/3.78	Obligation:
11.62/3.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
11.62/3.78	
11.62/3.78	
11.62/3.78	The TRS R consists of the following rules:
11.62/3.78	
11.62/3.78	   h(f(x), y) -> f(g(x, y))
11.62/3.78	   g(x, y) -> h(x, y)
11.62/3.78	
11.62/3.78	S is empty.
11.62/3.78	Rewrite Strategy: INNERMOST
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(1) RelTrsToTrsProof (UPPER BOUND(ID))
11.62/3.78	transformed relative TRS to TRS
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(2)
11.62/3.78	Obligation:
11.62/3.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
11.62/3.78	
11.62/3.78	
11.62/3.78	The TRS R consists of the following rules:
11.62/3.78	
11.62/3.78	   h(f(x), y) -> f(g(x, y))
11.62/3.78	   g(x, y) -> h(x, y)
11.62/3.78	
11.62/3.78	S is empty.
11.62/3.78	Rewrite Strategy: INNERMOST
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(3) CpxTrsMatchBoundsTAProof (FINISHED)
11.62/3.78	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 
11.62/3.78	
11.62/3.78	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
11.62/3.78	final states : [1, 2]
11.62/3.78	transitions: 
11.62/3.78	f0(0) -> 0
11.62/3.78	h0(0, 0) -> 1
11.62/3.78	g0(0, 0) -> 2
11.62/3.78	g1(0, 0) -> 3
11.62/3.78	f1(3) -> 1
11.62/3.78	h1(0, 0) -> 2
11.62/3.78	f1(3) -> 2
11.62/3.78	h2(0, 0) -> 3
11.62/3.78	f1(3) -> 3
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(4)
11.62/3.78	BOUNDS(1, n^1)
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(5) RenamingProof (BOTH BOUNDS(ID, ID))
11.62/3.78	Renamed function symbols to avoid clashes with predefined symbol.
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(6)
11.62/3.78	Obligation:
11.62/3.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
11.62/3.78	
11.62/3.78	
11.62/3.78	The TRS R consists of the following rules:
11.62/3.78	
11.62/3.78	   h(f(x), y) -> f(g(x, y))
11.62/3.78	   g(x, y) -> h(x, y)
11.62/3.78	
11.62/3.78	S is empty.
11.62/3.78	Rewrite Strategy: INNERMOST
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(7) SlicingProof (LOWER BOUND(ID))
11.62/3.78	Sliced the following arguments:
11.62/3.78	h/1
11.62/3.78	g/1
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(8)
11.62/3.78	Obligation:
11.62/3.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
11.62/3.78	
11.62/3.78	
11.62/3.78	The TRS R consists of the following rules:
11.62/3.78	
11.62/3.78	   h(f(x)) -> f(g(x))
11.62/3.78	   g(x) -> h(x)
11.62/3.78	
11.62/3.78	S is empty.
11.62/3.78	Rewrite Strategy: INNERMOST
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
11.62/3.78	Infered types.
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(10)
11.62/3.78	Obligation:
11.62/3.78	Innermost TRS:
11.62/3.78	Rules:
11.62/3.78	h(f(x)) -> f(g(x))
11.62/3.78	g(x) -> h(x)
11.62/3.78	
11.62/3.78	Types:
11.62/3.78	h :: f -> f
11.62/3.78	f :: f -> f
11.62/3.78	g :: f -> f
11.62/3.78	hole_f1_0 :: f
11.62/3.78	gen_f2_0 :: Nat -> f
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(11) OrderProof (LOWER BOUND(ID))
11.62/3.78	Heuristically decided to analyse the following defined symbols:
11.62/3.78	h, g
11.62/3.78	
11.62/3.78	They will be analysed ascendingly in the following order:
11.62/3.78	h = g
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(12)
11.62/3.78	Obligation:
11.62/3.78	Innermost TRS:
11.62/3.78	Rules:
11.62/3.78	h(f(x)) -> f(g(x))
11.62/3.78	g(x) -> h(x)
11.62/3.78	
11.62/3.78	Types:
11.62/3.78	h :: f -> f
11.62/3.78	f :: f -> f
11.62/3.78	g :: f -> f
11.62/3.78	hole_f1_0 :: f
11.62/3.78	gen_f2_0 :: Nat -> f
11.62/3.78	
11.62/3.78	
11.62/3.78	Generator Equations:
11.62/3.78	gen_f2_0(0) <=> hole_f1_0
11.62/3.78	gen_f2_0(+(x, 1)) <=> f(gen_f2_0(x))
11.62/3.78	
11.62/3.78	
11.62/3.78	The following defined symbols remain to be analysed:
11.62/3.78	g, h
11.62/3.78	
11.62/3.78	They will be analysed ascendingly in the following order:
11.62/3.78	h = g
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(13) RewriteLemmaProof (LOWER BOUND(ID))
11.62/3.78	Proved the following rewrite lemma:
11.62/3.78	g(gen_f2_0(n4_0)) -> *3_0, rt in Omega(n4_0)
11.62/3.78	
11.62/3.78	Induction Base:
11.62/3.78	g(gen_f2_0(0))
11.62/3.78	
11.62/3.78	Induction Step:
11.62/3.78	g(gen_f2_0(+(n4_0, 1))) ->_R^Omega(1)
11.62/3.78	h(gen_f2_0(+(n4_0, 1))) ->_R^Omega(1)
11.62/3.78	f(g(gen_f2_0(n4_0))) ->_IH
11.62/3.78	f(*3_0)
11.62/3.78	
11.62/3.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(14)
11.62/3.78	Complex Obligation (BEST)
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(15)
11.62/3.78	Obligation:
11.62/3.78	Proved the lower bound n^1 for the following obligation:
11.62/3.78	
11.62/3.78	Innermost TRS:
11.62/3.78	Rules:
11.62/3.78	h(f(x)) -> f(g(x))
11.62/3.78	g(x) -> h(x)
11.62/3.78	
11.62/3.78	Types:
11.62/3.78	h :: f -> f
11.62/3.78	f :: f -> f
11.62/3.78	g :: f -> f
11.62/3.78	hole_f1_0 :: f
11.62/3.78	gen_f2_0 :: Nat -> f
11.62/3.78	
11.62/3.78	
11.62/3.78	Generator Equations:
11.62/3.78	gen_f2_0(0) <=> hole_f1_0
11.62/3.78	gen_f2_0(+(x, 1)) <=> f(gen_f2_0(x))
11.62/3.78	
11.62/3.78	
11.62/3.78	The following defined symbols remain to be analysed:
11.62/3.78	g, h
11.62/3.78	
11.62/3.78	They will be analysed ascendingly in the following order:
11.62/3.78	h = g
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(16) LowerBoundPropagationProof (FINISHED)
11.62/3.78	Propagated lower bound.
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(17)
11.62/3.78	BOUNDS(n^1, INF)
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(18)
11.62/3.78	Obligation:
11.62/3.78	Innermost TRS:
11.62/3.78	Rules:
11.62/3.78	h(f(x)) -> f(g(x))
11.62/3.78	g(x) -> h(x)
11.62/3.78	
11.62/3.78	Types:
11.62/3.78	h :: f -> f
11.62/3.78	f :: f -> f
11.62/3.78	g :: f -> f
11.62/3.78	hole_f1_0 :: f
11.62/3.78	gen_f2_0 :: Nat -> f
11.62/3.78	
11.62/3.78	
11.62/3.78	Lemmas:
11.62/3.78	g(gen_f2_0(n4_0)) -> *3_0, rt in Omega(n4_0)
11.62/3.78	
11.62/3.78	
11.62/3.78	Generator Equations:
11.62/3.78	gen_f2_0(0) <=> hole_f1_0
11.62/3.78	gen_f2_0(+(x, 1)) <=> f(gen_f2_0(x))
11.62/3.78	
11.62/3.78	
11.62/3.78	The following defined symbols remain to be analysed:
11.62/3.78	h
11.62/3.78	
11.62/3.78	They will be analysed ascendingly in the following order:
11.62/3.78	h = g
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(19) RewriteLemmaProof (LOWER BOUND(ID))
11.62/3.78	Proved the following rewrite lemma:
11.62/3.78	h(gen_f2_0(+(1, n121_0))) -> *3_0, rt in Omega(n121_0)
11.62/3.78	
11.62/3.78	Induction Base:
11.62/3.78	h(gen_f2_0(+(1, 0)))
11.62/3.78	
11.62/3.78	Induction Step:
11.62/3.78	h(gen_f2_0(+(1, +(n121_0, 1)))) ->_R^Omega(1)
11.62/3.78	f(g(gen_f2_0(+(1, n121_0)))) ->_R^Omega(1)
11.62/3.78	f(h(gen_f2_0(+(1, n121_0)))) ->_IH
11.62/3.78	f(*3_0)
11.62/3.78	
11.62/3.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(20)
11.62/3.78	Obligation:
11.62/3.78	Innermost TRS:
11.62/3.78	Rules:
11.62/3.78	h(f(x)) -> f(g(x))
11.62/3.78	g(x) -> h(x)
11.62/3.78	
11.62/3.78	Types:
11.62/3.78	h :: f -> f
11.62/3.78	f :: f -> f
11.62/3.78	g :: f -> f
11.62/3.78	hole_f1_0 :: f
11.62/3.78	gen_f2_0 :: Nat -> f
11.62/3.78	
11.62/3.78	
11.62/3.78	Lemmas:
11.62/3.78	g(gen_f2_0(n4_0)) -> *3_0, rt in Omega(n4_0)
11.62/3.78	h(gen_f2_0(+(1, n121_0))) -> *3_0, rt in Omega(n121_0)
11.62/3.78	
11.62/3.78	
11.62/3.78	Generator Equations:
11.62/3.78	gen_f2_0(0) <=> hole_f1_0
11.62/3.78	gen_f2_0(+(x, 1)) <=> f(gen_f2_0(x))
11.62/3.78	
11.62/3.78	
11.62/3.78	The following defined symbols remain to be analysed:
11.62/3.78	g
11.62/3.78	
11.62/3.78	They will be analysed ascendingly in the following order:
11.62/3.78	h = g
11.62/3.78	
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(21) RewriteLemmaProof (LOWER BOUND(ID))
11.62/3.78	Proved the following rewrite lemma:
11.62/3.78	g(gen_f2_0(n355_0)) -> *3_0, rt in Omega(n355_0)
11.62/3.78	
11.62/3.78	Induction Base:
11.62/3.78	g(gen_f2_0(0))
11.62/3.78	
11.62/3.78	Induction Step:
11.62/3.78	g(gen_f2_0(+(n355_0, 1))) ->_R^Omega(1)
11.62/3.78	h(gen_f2_0(+(n355_0, 1))) ->_R^Omega(1)
11.62/3.78	f(g(gen_f2_0(n355_0))) ->_IH
11.62/3.78	f(*3_0)
11.62/3.78	
11.62/3.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.62/3.78	----------------------------------------
11.62/3.78	
11.62/3.78	(22)
11.62/3.78	BOUNDS(1, INF)
11.93/3.84	EOF