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