29.90/10.65	WORST_CASE(Omega(n^1), O(n^1))
29.90/10.66	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
29.90/10.66	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
29.90/10.66	
29.90/10.66	
29.90/10.66	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
29.90/10.66	
29.90/10.66	(0) CpxTRS
29.90/10.66	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	(2) CpxTRS
29.90/10.66	    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	    (4) CpxWeightedTrs
29.90/10.66	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	    (6) CpxTypedWeightedTrs
29.90/10.66	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
29.90/10.66	    (8) CpxTypedWeightedCompleteTrs
29.90/10.66	    (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	    (10) CpxTypedWeightedCompleteTrs
29.90/10.66	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
29.90/10.66	    (12) CpxRNTS
29.90/10.66	    (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	    (14) CpxRNTS
29.90/10.66	    (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
29.90/10.66	    (16) CpxRNTS
29.90/10.66	    (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
29.90/10.66	    (18) CpxRNTS
29.90/10.66	    (19) IntTrsBoundProof [UPPER BOUND(ID), 5067 ms]
29.90/10.66	    (20) CpxRNTS
29.90/10.66	    (21) IntTrsBoundProof [UPPER BOUND(ID), 149 ms]
29.90/10.66	    (22) CpxRNTS
29.90/10.66	    (23) FinalProof [FINISHED, 0 ms]
29.90/10.66	    (24) BOUNDS(1, n^1)
29.90/10.66	(25) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
29.90/10.66	(26) TRS for Loop Detection
29.90/10.66	    (27) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
29.90/10.66	    (28) BEST
29.90/10.66	        (29) proven lower bound
29.90/10.66	            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
29.90/10.66	            (31) BOUNDS(n^1, INF)
29.90/10.66	        (32) TRS for Loop Detection
29.90/10.66	
29.90/10.66	
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(0)
29.90/10.66	Obligation:
29.90/10.66	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
29.90/10.66	
29.90/10.66	
29.90/10.66	The TRS R consists of the following rules:
29.90/10.66	
29.90/10.66	   D(t) -> 1
29.90/10.66	   D(constant) -> 0
29.90/10.66	   D(+(x, y)) -> +(D(x), D(y))
29.90/10.66	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y)))
29.90/10.66	   D(-(x, y)) -> -(D(x), D(y))
29.90/10.66	   D(minus(x)) -> minus(D(x))
29.90/10.66	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2)))
29.90/10.66	   D(ln(x)) -> div(D(x), x)
29.90/10.66	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y)))
29.90/10.66	
29.90/10.66	S is empty.
29.90/10.66	Rewrite Strategy: FULL
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
29.90/10.66	Converted rc-obligation to irc-obligation.
29.90/10.66	
29.90/10.66	As the TRS does not nest defined symbols, we have rc = irc.
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(2)
29.90/10.66	Obligation:
29.90/10.66	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
29.90/10.66	
29.90/10.66	
29.90/10.66	The TRS R consists of the following rules:
29.90/10.66	
29.90/10.66	   D(t) -> 1
29.90/10.66	   D(constant) -> 0
29.90/10.66	   D(+(x, y)) -> +(D(x), D(y))
29.90/10.66	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y)))
29.90/10.66	   D(-(x, y)) -> -(D(x), D(y))
29.90/10.66	   D(minus(x)) -> minus(D(x))
29.90/10.66	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2)))
29.90/10.66	   D(ln(x)) -> div(D(x), x)
29.90/10.66	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y)))
29.90/10.66	
29.90/10.66	S is empty.
29.90/10.66	Rewrite Strategy: INNERMOST
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
29.90/10.66	Transformed relative TRS to weighted TRS
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(4)
29.90/10.66	Obligation:
29.90/10.66	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
29.90/10.66	
29.90/10.66	
29.90/10.66	The TRS R consists of the following rules:
29.90/10.66	
29.90/10.66	   D(t) -> 1 [1]
29.90/10.66	   D(constant) -> 0 [1]
29.90/10.66	   D(+(x, y)) -> +(D(x), D(y)) [1]
29.90/10.66	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1]
29.90/10.66	   D(-(x, y)) -> -(D(x), D(y)) [1]
29.90/10.66	   D(minus(x)) -> minus(D(x)) [1]
29.90/10.66	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2))) [1]
29.90/10.66	   D(ln(x)) -> div(D(x), x) [1]
29.90/10.66	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y))) [1]
29.90/10.66	
29.90/10.66	Rewrite Strategy: INNERMOST
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
29.90/10.66	Infered types.
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(6)
29.90/10.66	Obligation:
29.90/10.66	Runtime Complexity Weighted TRS with Types.
29.90/10.66	The TRS R consists of the following rules:
29.90/10.66	
29.90/10.66	   D(t) -> 1 [1]
29.90/10.66	   D(constant) -> 0 [1]
29.90/10.66	   D(+(x, y)) -> +(D(x), D(y)) [1]
29.90/10.66	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1]
29.90/10.66	   D(-(x, y)) -> -(D(x), D(y)) [1]
29.90/10.66	   D(minus(x)) -> minus(D(x)) [1]
29.90/10.66	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2))) [1]
29.90/10.66	   D(ln(x)) -> div(D(x), x) [1]
29.90/10.66	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y))) [1]
29.90/10.66	
29.90/10.66	The TRS has the following type information:
29.90/10.66	D :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	t :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	1 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	constant :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	0 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	+ :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	* :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	- :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	minus :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	div :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	pow :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	2 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	ln :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.66	
29.90/10.66	Rewrite Strategy: INNERMOST
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(7) CompletionProof (UPPER BOUND(ID))
29.90/10.66	The transformation into a RNTS is sound, since:
29.90/10.66	
29.90/10.66	(a) The obligation is a constructor system where every type has a constant constructor,
29.90/10.66	
29.90/10.66	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
29.90/10.66	
29.90/10.66	   D_1
29.90/10.66	
29.90/10.66	(c) The following functions are completely defined:
29.90/10.66	none
29.90/10.66	
29.90/10.66	Due to the following rules being added:
29.90/10.66	none
29.90/10.66	
29.90/10.66	And the following fresh constants: none
29.90/10.66	
29.90/10.66	----------------------------------------
29.90/10.66	
29.90/10.66	(8)
29.90/10.66	Obligation:
29.90/10.66	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
29.90/10.66	
29.90/10.66	Runtime Complexity Weighted TRS with Types.
29.90/10.66	The TRS R consists of the following rules:
29.90/10.67	
29.90/10.67	   D(t) -> 1 [1]
29.90/10.67	   D(constant) -> 0 [1]
29.90/10.67	   D(+(x, y)) -> +(D(x), D(y)) [1]
29.90/10.67	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1]
29.90/10.67	   D(-(x, y)) -> -(D(x), D(y)) [1]
29.90/10.67	   D(minus(x)) -> minus(D(x)) [1]
29.90/10.67	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2))) [1]
29.90/10.67	   D(ln(x)) -> div(D(x), x) [1]
29.90/10.67	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y))) [1]
29.90/10.67	
29.90/10.67	The TRS has the following type information:
29.90/10.67	D :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	t :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	1 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	constant :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	0 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	+ :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	* :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	- :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	minus :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	div :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	pow :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	2 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	ln :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	
29.90/10.67	Rewrite Strategy: INNERMOST
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(9) NarrowingProof (BOTH BOUNDS(ID, ID))
29.90/10.67	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(10)
29.90/10.67	Obligation:
29.90/10.67	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
29.90/10.67	
29.90/10.67	Runtime Complexity Weighted TRS with Types.
29.90/10.67	The TRS R consists of the following rules:
29.90/10.67	
29.90/10.67	   D(t) -> 1 [1]
29.90/10.67	   D(constant) -> 0 [1]
29.90/10.67	   D(+(x, y)) -> +(D(x), D(y)) [1]
29.90/10.67	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1]
29.90/10.67	   D(-(x, y)) -> -(D(x), D(y)) [1]
29.90/10.67	   D(minus(x)) -> minus(D(x)) [1]
29.90/10.67	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2))) [1]
29.90/10.67	   D(ln(x)) -> div(D(x), x) [1]
29.90/10.67	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y))) [1]
29.90/10.67	
29.90/10.67	The TRS has the following type information:
29.90/10.67	D :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	t :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	1 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	constant :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	0 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	+ :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	* :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	- :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	minus :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	div :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	pow :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	2 :: t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	ln :: t:1:constant:0:+:*:-:minus:div:2:pow:ln -> t:1:constant:0:+:*:-:minus:div:2:pow:ln
29.90/10.67	
29.90/10.67	Rewrite Strategy: INNERMOST
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
29.90/10.67	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
29.90/10.67	The constant constructors are abstracted as follows:
29.90/10.67	
29.90/10.67	   t => 4
29.90/10.67	   1 => 1
29.90/10.67	   constant => 3
29.90/10.67	   0 => 0
29.90/10.67	   2 => 2
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(12)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) :|: x >= 0, z = 1 + x
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + x :|: x >= 0, z = 1 + x
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(13) SimplificationProof (BOTH BOUNDS(ID, ID))
29.90/10.67	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(14)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) + (z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
29.90/10.67	Found the following analysis order by SCC decomposition:
29.90/10.67	
29.90/10.67	   { D }
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(16)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) + (z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	Function symbols to be analyzed: {D}
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(17) ResultPropagationProof (UPPER BOUND(ID))
29.90/10.67	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(18)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) + (z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	Function symbols to be analyzed: {D}
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(19) IntTrsBoundProof (UPPER BOUND(ID))
29.90/10.67	
29.90/10.67	Computed SIZE bound using KoAT for: D
29.90/10.67	after applying outer abstraction to obtain an ITS,
29.90/10.67	resulting in: O(n^2) with polynomial bound: 23*z + 12*z^2
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(20)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) + (z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	Function symbols to be analyzed: {D}
29.90/10.67	Previous analysis results are:
29.90/10.67	  D: runtime: ?, size: O(n^2) [23*z + 12*z^2]
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(21) IntTrsBoundProof (UPPER BOUND(ID))
29.90/10.67	
29.90/10.67	Computed RUNTIME bound using CoFloCo for: D
29.90/10.67	after applying outer abstraction to obtain an ITS,
29.90/10.67	resulting in: O(n^1) with polynomial bound: 1 + z
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(22)
29.90/10.67	Obligation:
29.90/10.67	Complexity RNTS consisting of the following rules:
29.90/10.67	
29.90/10.67	   D(z) -{ 1 }-> 1 :|: z = 4
29.90/10.67	   D(z) -{ 1 }-> 0 :|: z = 3
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + D(z - 1) + (z - 1) :|: z - 1 >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + D(x) + y) + (1 + (1 + x + D(y)) + (1 + y + 2)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	   D(z) -{ 1 }-> 1 + (1 + (1 + y + (1 + x + (1 + y + 1))) + D(x)) + (1 + (1 + (1 + x + y) + (1 + x)) + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0
29.90/10.67	
29.90/10.67	Function symbols to be analyzed: 
29.90/10.67	Previous analysis results are:
29.90/10.67	  D: runtime: O(n^1) [1 + z], size: O(n^2) [23*z + 12*z^2]
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(23) FinalProof (FINISHED)
29.90/10.67	Computed overall runtime complexity
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(24)
29.90/10.67	BOUNDS(1, n^1)
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(25) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
29.90/10.67	Transformed a relative TRS into a decreasing-loop problem.
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(26)
29.90/10.67	Obligation:
29.90/10.67	Analyzing the following TRS for decreasing loops:
29.90/10.67	
29.90/10.67	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
29.90/10.67	
29.90/10.67	
29.90/10.67	The TRS R consists of the following rules:
29.90/10.67	
29.90/10.67	   D(t) -> 1
29.90/10.67	   D(constant) -> 0
29.90/10.67	   D(+(x, y)) -> +(D(x), D(y))
29.90/10.67	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y)))
29.90/10.67	   D(-(x, y)) -> -(D(x), D(y))
29.90/10.67	   D(minus(x)) -> minus(D(x))
29.90/10.67	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2)))
29.90/10.67	   D(ln(x)) -> div(D(x), x)
29.90/10.67	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y)))
29.90/10.67	
29.90/10.67	S is empty.
29.90/10.67	Rewrite Strategy: FULL
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(27) DecreasingLoopProof (LOWER BOUND(ID))
29.90/10.67	The following loop(s) give(s) rise to the lower bound Omega(n^1):
29.90/10.67	
29.90/10.67	The rewrite sequence
29.90/10.67	
29.90/10.67	D(+(x, y)) ->^+ +(D(x), D(y))
29.90/10.67	
29.90/10.67	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
29.90/10.67	
29.90/10.67	The pumping substitution is [x / +(x, y)].
29.90/10.67	
29.90/10.67	The result substitution is [ ].
29.90/10.67	
29.90/10.67	
29.90/10.67	
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(28)
29.90/10.67	Complex Obligation (BEST)
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(29)
29.90/10.67	Obligation:
29.90/10.67	Proved the lower bound n^1 for the following obligation:
29.90/10.67	
29.90/10.67	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
29.90/10.67	
29.90/10.67	
29.90/10.67	The TRS R consists of the following rules:
29.90/10.67	
29.90/10.67	   D(t) -> 1
29.90/10.67	   D(constant) -> 0
29.90/10.67	   D(+(x, y)) -> +(D(x), D(y))
29.90/10.67	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y)))
29.90/10.67	   D(-(x, y)) -> -(D(x), D(y))
29.90/10.67	   D(minus(x)) -> minus(D(x))
29.90/10.67	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2)))
29.90/10.67	   D(ln(x)) -> div(D(x), x)
29.90/10.67	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y)))
29.90/10.67	
29.90/10.67	S is empty.
29.90/10.67	Rewrite Strategy: FULL
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(30) LowerBoundPropagationProof (FINISHED)
29.90/10.67	Propagated lower bound.
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(31)
29.90/10.67	BOUNDS(n^1, INF)
29.90/10.67	
29.90/10.67	----------------------------------------
29.90/10.67	
29.90/10.67	(32)
29.90/10.67	Obligation:
29.90/10.67	Analyzing the following TRS for decreasing loops:
29.90/10.67	
29.90/10.67	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
29.90/10.67	
29.90/10.67	
29.90/10.67	The TRS R consists of the following rules:
29.90/10.67	
29.90/10.67	   D(t) -> 1
29.90/10.67	   D(constant) -> 0
29.90/10.67	   D(+(x, y)) -> +(D(x), D(y))
29.90/10.67	   D(*(x, y)) -> +(*(y, D(x)), *(x, D(y)))
29.90/10.67	   D(-(x, y)) -> -(D(x), D(y))
29.90/10.67	   D(minus(x)) -> minus(D(x))
29.90/10.67	   D(div(x, y)) -> -(div(D(x), y), div(*(x, D(y)), pow(y, 2)))
29.90/10.67	   D(ln(x)) -> div(D(x), x)
29.90/10.67	   D(pow(x, y)) -> +(*(*(y, pow(x, -(y, 1))), D(x)), *(*(pow(x, y), ln(x)), D(y)))
29.90/10.67	
29.90/10.67	S is empty.
29.90/10.67	Rewrite Strategy: FULL
30.11/10.71	EOF