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