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