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