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