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