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