16.39/5.22	WORST_CASE(Omega(n^1), O(n^1))
16.39/5.23	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
16.39/5.23	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.39/5.23	
16.39/5.23	
16.39/5.23	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.39/5.23	
16.39/5.23	(0) CpxTRS
16.39/5.23	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	(2) CpxTRS
16.39/5.23	    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (4) CpxWeightedTrs
16.39/5.23	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (6) CpxTypedWeightedTrs
16.39/5.23	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
16.39/5.23	    (8) CpxTypedWeightedCompleteTrs
16.39/5.23	    (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (10) CpxTypedWeightedCompleteTrs
16.39/5.23	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
16.39/5.23	    (12) CpxRNTS
16.39/5.23	    (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (14) CpxRNTS
16.39/5.23	    (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (16) CpxRNTS
16.39/5.23	    (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
16.39/5.23	    (18) CpxRNTS
16.39/5.23	    (19) IntTrsBoundProof [UPPER BOUND(ID), 423 ms]
16.39/5.23	    (20) CpxRNTS
16.39/5.23	    (21) IntTrsBoundProof [UPPER BOUND(ID), 139 ms]
16.39/5.23	    (22) CpxRNTS
16.39/5.23	    (23) FinalProof [FINISHED, 0 ms]
16.39/5.23	    (24) BOUNDS(1, n^1)
16.39/5.23	(25) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	(26) CpxTRS
16.39/5.23	    (27) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
16.39/5.23	    (28) typed CpxTrs
16.39/5.23	    (29) OrderProof [LOWER BOUND(ID), 0 ms]
16.39/5.23	    (30) typed CpxTrs
16.39/5.23	    (31) RewriteLemmaProof [LOWER BOUND(ID), 483 ms]
16.39/5.23	    (32) proven lower bound
16.39/5.23	    (33) LowerBoundPropagationProof [FINISHED, 0 ms]
16.39/5.23	    (34) BOUNDS(n^1, INF)
16.39/5.23	
16.39/5.23	
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(0)
16.39/5.23	Obligation:
16.39/5.23	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.39/5.23	
16.39/5.23	
16.39/5.23	The TRS R consists of the following rules:
16.39/5.23	
16.39/5.23	   f(x, g(x)) -> x
16.39/5.23	   f(x, h(y)) -> f(h(x), y)
16.39/5.23	
16.39/5.23	S is empty.
16.39/5.23	Rewrite Strategy: FULL
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
16.39/5.23	Converted rc-obligation to irc-obligation.
16.39/5.23	
16.39/5.23	As the TRS does not nest defined symbols, we have rc = irc.
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(2)
16.39/5.23	Obligation:
16.39/5.23	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.39/5.23	
16.39/5.23	
16.39/5.23	The TRS R consists of the following rules:
16.39/5.23	
16.39/5.23	   f(x, g(x)) -> x
16.39/5.23	   f(x, h(y)) -> f(h(x), y)
16.39/5.23	
16.39/5.23	S is empty.
16.39/5.23	Rewrite Strategy: INNERMOST
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
16.39/5.23	Transformed relative TRS to weighted TRS
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(4)
16.39/5.23	Obligation:
16.39/5.23	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
16.39/5.23	
16.39/5.23	
16.39/5.23	The TRS R consists of the following rules:
16.39/5.23	
16.39/5.23	   f(x, g(x)) -> x [1]
16.39/5.23	   f(x, h(y)) -> f(h(x), y) [1]
16.39/5.23	
16.39/5.23	Rewrite Strategy: INNERMOST
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
16.39/5.23	Infered types.
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(6)
16.39/5.23	Obligation:
16.39/5.23	Runtime Complexity Weighted TRS with Types.
16.39/5.23	The TRS R consists of the following rules:
16.39/5.23	
16.39/5.23	   f(x, g(x)) -> x [1]
16.39/5.23	   f(x, h(y)) -> f(h(x), y) [1]
16.39/5.23	
16.39/5.23	The TRS has the following type information:
16.39/5.23	f :: g:h -> g:h -> g:h
16.39/5.23	g :: g:h -> g:h
16.39/5.23	h :: g:h -> g:h
16.39/5.23	
16.39/5.23	Rewrite Strategy: INNERMOST
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(7) CompletionProof (UPPER BOUND(ID))
16.39/5.23	The transformation into a RNTS is sound, since:
16.39/5.23	
16.39/5.23	(a) The obligation is a constructor system where every type has a constant constructor,
16.39/5.23	
16.39/5.23	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
16.39/5.23	
16.39/5.23	   f_2
16.39/5.23	
16.39/5.23	(c) The following functions are completely defined:
16.39/5.23	none
16.39/5.23	
16.39/5.23	Due to the following rules being added:
16.39/5.23	none
16.39/5.23	
16.39/5.23	And the following fresh constants:    const
16.39/5.23	
16.39/5.23	----------------------------------------
16.39/5.23	
16.39/5.23	(8)
16.39/5.23	Obligation:
16.39/5.23	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
16.39/5.23	
16.39/5.23	Runtime Complexity Weighted TRS with Types.
16.39/5.23	The TRS R consists of the following rules:
16.39/5.23	
16.39/5.23	   f(x, g(x)) -> x [1]
16.39/5.23	   f(x, h(y)) -> f(h(x), y) [1]
16.39/5.23	
16.39/5.23	The TRS has the following type information:
16.39/5.23	f :: g:h -> g:h -> g:h
16.39/5.23	g :: g:h -> g:h
16.39/5.23	h :: g:h -> g:h
16.39/5.23	const :: g:h
16.39/5.23	
16.39/5.23	Rewrite Strategy: INNERMOST
16.39/5.23	----------------------------------------
16.39/5.24	
16.39/5.24	(9) NarrowingProof (BOTH BOUNDS(ID, ID))
16.39/5.24	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(10)
16.39/5.24	Obligation:
16.39/5.24	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
16.39/5.24	
16.39/5.24	Runtime Complexity Weighted TRS with Types.
16.39/5.24	The TRS R consists of the following rules:
16.39/5.24	
16.39/5.24	   f(x, g(x)) -> x [1]
16.39/5.24	   f(x, h(y)) -> f(h(x), y) [1]
16.39/5.24	
16.39/5.24	The TRS has the following type information:
16.39/5.24	f :: g:h -> g:h -> g:h
16.39/5.24	g :: g:h -> g:h
16.39/5.24	h :: g:h -> g:h
16.39/5.24	const :: g:h
16.39/5.24	
16.39/5.24	Rewrite Strategy: INNERMOST
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
16.39/5.24	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
16.39/5.24	The constant constructors are abstracted as follows:
16.39/5.24	
16.39/5.24	   const => 0
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(12)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> x :|: z' = 1 + x, x >= 0, z = x
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = x
16.39/5.24	
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(13) SimplificationProof (BOTH BOUNDS(ID, ID))
16.39/5.24	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(14)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + z, z' - 1) :|: z >= 0, z' - 1 >= 0
16.39/5.24	   f(z, z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0, z = z' - 1
16.39/5.24	
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
16.39/5.24	Found the following analysis order by SCC decomposition:
16.39/5.24	
16.39/5.24	   { f }
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(16)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + z, z' - 1) :|: z >= 0, z' - 1 >= 0
16.39/5.24	   f(z, z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0, z = z' - 1
16.39/5.24	
16.39/5.24	Function symbols to be analyzed: {f}
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(17) ResultPropagationProof (UPPER BOUND(ID))
16.39/5.24	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(18)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + z, z' - 1) :|: z >= 0, z' - 1 >= 0
16.39/5.24	   f(z, z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0, z = z' - 1
16.39/5.24	
16.39/5.24	Function symbols to be analyzed: {f}
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(19) IntTrsBoundProof (UPPER BOUND(ID))
16.39/5.24	
16.39/5.24	Computed SIZE bound using KoAT for: f
16.39/5.24	after applying outer abstraction to obtain an ITS,
16.39/5.24	resulting in: O(n^1) with polynomial bound: z'
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(20)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + z, z' - 1) :|: z >= 0, z' - 1 >= 0
16.39/5.24	   f(z, z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0, z = z' - 1
16.39/5.24	
16.39/5.24	Function symbols to be analyzed: {f}
16.39/5.24	Previous analysis results are:
16.39/5.24	  f: runtime: ?, size: O(n^1) [z']
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(21) IntTrsBoundProof (UPPER BOUND(ID))
16.39/5.24	
16.39/5.24	Computed RUNTIME bound using KoAT for: f
16.39/5.24	after applying outer abstraction to obtain an ITS,
16.39/5.24	resulting in: O(n^1) with polynomial bound: 1 + z'
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(22)
16.39/5.24	Obligation:
16.39/5.24	Complexity RNTS consisting of the following rules:
16.39/5.24	
16.39/5.24	   f(z, z') -{ 1 }-> f(1 + z, z' - 1) :|: z >= 0, z' - 1 >= 0
16.39/5.24	   f(z, z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0, z = z' - 1
16.39/5.24	
16.39/5.24	Function symbols to be analyzed: 
16.39/5.24	Previous analysis results are:
16.39/5.24	  f: runtime: O(n^1) [1 + z'], size: O(n^1) [z']
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(23) FinalProof (FINISHED)
16.39/5.24	Computed overall runtime complexity
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(24)
16.39/5.24	BOUNDS(1, n^1)
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(25) RenamingProof (BOTH BOUNDS(ID, ID))
16.39/5.24	Renamed function symbols to avoid clashes with predefined symbol.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(26)
16.39/5.24	Obligation:
16.39/5.24	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
16.39/5.24	
16.39/5.24	
16.39/5.24	The TRS R consists of the following rules:
16.39/5.24	
16.39/5.24	   f(x, g(x)) -> x
16.39/5.24	   f(x, h(y)) -> f(h(x), y)
16.39/5.24	
16.39/5.24	S is empty.
16.39/5.24	Rewrite Strategy: FULL
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(27) TypeInferenceProof (BOTH BOUNDS(ID, ID))
16.39/5.24	Infered types.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(28)
16.39/5.24	Obligation:
16.39/5.24	TRS:
16.39/5.24	Rules:
16.39/5.24	f(x, g(x)) -> x
16.39/5.24	f(x, h(y)) -> f(h(x), y)
16.39/5.24	
16.39/5.24	Types:
16.39/5.24	f :: g:h -> g:h -> g:h
16.39/5.24	g :: g:h -> g:h
16.39/5.24	h :: g:h -> g:h
16.39/5.24	hole_g:h1_0 :: g:h
16.39/5.24	gen_g:h2_0 :: Nat -> g:h
16.39/5.24	
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(29) OrderProof (LOWER BOUND(ID))
16.39/5.24	Heuristically decided to analyse the following defined symbols:
16.39/5.24	f
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(30)
16.39/5.24	Obligation:
16.39/5.24	TRS:
16.39/5.24	Rules:
16.39/5.24	f(x, g(x)) -> x
16.39/5.24	f(x, h(y)) -> f(h(x), y)
16.39/5.24	
16.39/5.24	Types:
16.39/5.24	f :: g:h -> g:h -> g:h
16.39/5.24	g :: g:h -> g:h
16.39/5.24	h :: g:h -> g:h
16.39/5.24	hole_g:h1_0 :: g:h
16.39/5.24	gen_g:h2_0 :: Nat -> g:h
16.39/5.24	
16.39/5.24	
16.39/5.24	Generator Equations:
16.39/5.24	gen_g:h2_0(0) <=> hole_g:h1_0
16.39/5.24	gen_g:h2_0(+(x, 1)) <=> h(gen_g:h2_0(x))
16.39/5.24	
16.39/5.24	
16.39/5.24	The following defined symbols remain to be analysed:
16.39/5.24	f
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(31) RewriteLemmaProof (LOWER BOUND(ID))
16.39/5.24	Proved the following rewrite lemma:
16.39/5.24	f(gen_g:h2_0(a), gen_g:h2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
16.39/5.24	
16.39/5.24	Induction Base:
16.39/5.24	f(gen_g:h2_0(a), gen_g:h2_0(+(1, 0)))
16.39/5.24	
16.39/5.24	Induction Step:
16.39/5.24	f(gen_g:h2_0(a), gen_g:h2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
16.39/5.24	f(h(gen_g:h2_0(a)), gen_g:h2_0(+(1, n4_0))) ->_IH
16.39/5.24	*3_0
16.39/5.24	
16.39/5.24	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(32)
16.39/5.24	Obligation:
16.39/5.24	Proved the lower bound n^1 for the following obligation:
16.39/5.24	
16.39/5.24	TRS:
16.39/5.24	Rules:
16.39/5.24	f(x, g(x)) -> x
16.39/5.24	f(x, h(y)) -> f(h(x), y)
16.39/5.24	
16.39/5.24	Types:
16.39/5.24	f :: g:h -> g:h -> g:h
16.39/5.24	g :: g:h -> g:h
16.39/5.24	h :: g:h -> g:h
16.39/5.24	hole_g:h1_0 :: g:h
16.39/5.24	gen_g:h2_0 :: Nat -> g:h
16.39/5.24	
16.39/5.24	
16.39/5.24	Generator Equations:
16.39/5.24	gen_g:h2_0(0) <=> hole_g:h1_0
16.39/5.24	gen_g:h2_0(+(x, 1)) <=> h(gen_g:h2_0(x))
16.39/5.24	
16.39/5.24	
16.39/5.24	The following defined symbols remain to be analysed:
16.39/5.24	f
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(33) LowerBoundPropagationProof (FINISHED)
16.39/5.24	Propagated lower bound.
16.39/5.24	----------------------------------------
16.39/5.24	
16.39/5.24	(34)
16.39/5.24	BOUNDS(n^1, INF)
16.39/5.27	EOF