17.01/5.15	WORST_CASE(Omega(n^1), O(n^1))
17.01/5.17	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
17.01/5.17	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
17.01/5.17	
17.01/5.17	
17.01/5.17	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.01/5.17	
17.01/5.17	(0) CpxTRS
17.01/5.17	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
17.01/5.17	(2) CpxTRS
17.01/5.17	    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
17.01/5.17	    (4) CpxWeightedTrs
17.01/5.17	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
17.01/5.17	    (6) CpxTypedWeightedTrs
17.01/5.17	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
17.01/5.17	    (8) CpxTypedWeightedCompleteTrs
17.01/5.17	    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 3 ms]
17.01/5.17	    (10) CpxRNTS
17.01/5.17	    (11) CompleteCoflocoProof [FINISHED, 516 ms]
17.01/5.17	    (12) BOUNDS(1, n^1)
17.01/5.17	(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
17.01/5.17	(14) TRS for Loop Detection
17.01/5.17	    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
17.01/5.17	    (16) BEST
17.01/5.17	        (17) proven lower bound
17.01/5.17	            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
17.01/5.17	            (19) BOUNDS(n^1, INF)
17.01/5.17	        (20) TRS for Loop Detection
17.01/5.17	
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(0)
17.01/5.17	Obligation:
17.01/5.17	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X)
17.01/5.17	   a__and(false, Y) -> false
17.01/5.17	   a__if(true, X, Y) -> mark(X)
17.01/5.17	   a__if(false, X, Y) -> mark(Y)
17.01/5.17	   a__add(0, X) -> mark(X)
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y))
17.01/5.17	   a__first(0, X) -> nil
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
17.01/5.17	   a__from(X) -> cons(X, from(s(X)))
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
17.01/5.17	   mark(from(X)) -> a__from(X)
17.01/5.17	   mark(true) -> true
17.01/5.17	   mark(false) -> false
17.01/5.17	   mark(0) -> 0
17.01/5.17	   mark(s(X)) -> s(X)
17.01/5.17	   mark(nil) -> nil
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2)
17.01/5.17	   a__and(X1, X2) -> and(X1, X2)
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3)
17.01/5.17	   a__add(X1, X2) -> add(X1, X2)
17.01/5.17	   a__first(X1, X2) -> first(X1, X2)
17.01/5.17	   a__from(X) -> from(X)
17.01/5.17	
17.01/5.17	S is empty.
17.01/5.17	Rewrite Strategy: FULL
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
17.01/5.17	Converted rc-obligation to irc-obligation.
17.01/5.17	
17.01/5.17	The duplicating contexts are:
17.01/5.17	a__from([])
17.01/5.17	
17.01/5.17	
17.01/5.17	The defined contexts are:
17.01/5.17	a__first([], x1)
17.01/5.17	a__first(x0, [])
17.01/5.17	a__add([], x1)
17.01/5.17	a__and([], x1)
17.01/5.17	a__if([], x1, x2)
17.01/5.17	
17.01/5.17	
17.01/5.17	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(2)
17.01/5.17	Obligation:
17.01/5.17	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X)
17.01/5.17	   a__and(false, Y) -> false
17.01/5.17	   a__if(true, X, Y) -> mark(X)
17.01/5.17	   a__if(false, X, Y) -> mark(Y)
17.01/5.17	   a__add(0, X) -> mark(X)
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y))
17.01/5.17	   a__first(0, X) -> nil
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
17.01/5.17	   a__from(X) -> cons(X, from(s(X)))
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
17.01/5.17	   mark(from(X)) -> a__from(X)
17.01/5.17	   mark(true) -> true
17.01/5.17	   mark(false) -> false
17.01/5.17	   mark(0) -> 0
17.01/5.17	   mark(s(X)) -> s(X)
17.01/5.17	   mark(nil) -> nil
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2)
17.01/5.17	   a__and(X1, X2) -> and(X1, X2)
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3)
17.01/5.17	   a__add(X1, X2) -> add(X1, X2)
17.01/5.17	   a__first(X1, X2) -> first(X1, X2)
17.01/5.17	   a__from(X) -> from(X)
17.01/5.17	
17.01/5.17	S is empty.
17.01/5.17	Rewrite Strategy: INNERMOST
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
17.01/5.17	Transformed relative TRS to weighted TRS
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(4)
17.01/5.17	Obligation:
17.01/5.17	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X) [1]
17.01/5.17	   a__and(false, Y) -> false [1]
17.01/5.17	   a__if(true, X, Y) -> mark(X) [1]
17.01/5.17	   a__if(false, X, Y) -> mark(Y) [1]
17.01/5.17	   a__add(0, X) -> mark(X) [1]
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y)) [1]
17.01/5.17	   a__first(0, X) -> nil [1]
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1]
17.01/5.17	   a__from(X) -> cons(X, from(s(X))) [1]
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2) [1]
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1]
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2) [1]
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1]
17.01/5.17	   mark(from(X)) -> a__from(X) [1]
17.01/5.17	   mark(true) -> true [1]
17.01/5.17	   mark(false) -> false [1]
17.01/5.17	   mark(0) -> 0 [1]
17.01/5.17	   mark(s(X)) -> s(X) [1]
17.01/5.17	   mark(nil) -> nil [1]
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2) [1]
17.01/5.17	   a__and(X1, X2) -> and(X1, X2) [1]
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3) [1]
17.01/5.17	   a__add(X1, X2) -> add(X1, X2) [1]
17.01/5.17	   a__first(X1, X2) -> first(X1, X2) [1]
17.01/5.17	   a__from(X) -> from(X) [1]
17.01/5.17	
17.01/5.17	Rewrite Strategy: INNERMOST
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
17.01/5.17	Infered types.
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(6)
17.01/5.17	Obligation:
17.01/5.17	Runtime Complexity Weighted TRS with Types.
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X) [1]
17.01/5.17	   a__and(false, Y) -> false [1]
17.01/5.17	   a__if(true, X, Y) -> mark(X) [1]
17.01/5.17	   a__if(false, X, Y) -> mark(Y) [1]
17.01/5.17	   a__add(0, X) -> mark(X) [1]
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y)) [1]
17.01/5.17	   a__first(0, X) -> nil [1]
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1]
17.01/5.17	   a__from(X) -> cons(X, from(s(X))) [1]
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2) [1]
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1]
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2) [1]
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1]
17.01/5.17	   mark(from(X)) -> a__from(X) [1]
17.01/5.17	   mark(true) -> true [1]
17.01/5.17	   mark(false) -> false [1]
17.01/5.17	   mark(0) -> 0 [1]
17.01/5.17	   mark(s(X)) -> s(X) [1]
17.01/5.17	   mark(nil) -> nil [1]
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2) [1]
17.01/5.17	   a__and(X1, X2) -> and(X1, X2) [1]
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3) [1]
17.01/5.17	   a__add(X1, X2) -> add(X1, X2) [1]
17.01/5.17	   a__first(X1, X2) -> first(X1, X2) [1]
17.01/5.17	   a__from(X) -> from(X) [1]
17.01/5.17	
17.01/5.17	The TRS has the following type information:
17.01/5.17	a__and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	true :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	false :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	0 :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	nil :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	cons :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	
17.01/5.17	Rewrite Strategy: INNERMOST
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(7) CompletionProof (UPPER BOUND(ID))
17.01/5.17	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
17.01/5.17	none
17.01/5.17	
17.01/5.17	And the following fresh constants: none
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(8)
17.01/5.17	Obligation:
17.01/5.17	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
17.01/5.17	
17.01/5.17	Runtime Complexity Weighted TRS with Types.
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X) [1]
17.01/5.17	   a__and(false, Y) -> false [1]
17.01/5.17	   a__if(true, X, Y) -> mark(X) [1]
17.01/5.17	   a__if(false, X, Y) -> mark(Y) [1]
17.01/5.17	   a__add(0, X) -> mark(X) [1]
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y)) [1]
17.01/5.17	   a__first(0, X) -> nil [1]
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1]
17.01/5.17	   a__from(X) -> cons(X, from(s(X))) [1]
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2) [1]
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1]
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2) [1]
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1]
17.01/5.17	   mark(from(X)) -> a__from(X) [1]
17.01/5.17	   mark(true) -> true [1]
17.01/5.17	   mark(false) -> false [1]
17.01/5.17	   mark(0) -> 0 [1]
17.01/5.17	   mark(s(X)) -> s(X) [1]
17.01/5.17	   mark(nil) -> nil [1]
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2) [1]
17.01/5.17	   a__and(X1, X2) -> and(X1, X2) [1]
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3) [1]
17.01/5.17	   a__add(X1, X2) -> add(X1, X2) [1]
17.01/5.17	   a__first(X1, X2) -> first(X1, X2) [1]
17.01/5.17	   a__from(X) -> from(X) [1]
17.01/5.17	
17.01/5.17	The TRS has the following type information:
17.01/5.17	a__and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	true :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	false :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	0 :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	nil :: true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	cons :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if
17.01/5.17	
17.01/5.17	Rewrite Strategy: INNERMOST
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
17.01/5.17	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
17.01/5.17	The constant constructors are abstracted as follows:
17.01/5.17	
17.01/5.17	   true => 3
17.01/5.17	   false => 1
17.01/5.17	   0 => 0
17.01/5.17	   nil => 2
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(10)
17.01/5.17	Obligation:
17.01/5.17	Complexity RNTS consisting of the following rules:
17.01/5.17	
17.01/5.17	   a__add(z, z') -{ 1 }-> mark(X) :|: z' = X, X >= 0, z = 0
17.01/5.17	   a__add(z, z') -{ 1 }-> 1 + (1 + X + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0
17.01/5.17	   a__add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
17.01/5.17	   a__and(z, z') -{ 1 }-> mark(X) :|: z' = X, z = 3, X >= 0
17.01/5.17	   a__and(z, z') -{ 1 }-> 1 :|: z' = Y, Y >= 0, z = 1
17.01/5.17	   a__and(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
17.01/5.17	   a__first(z, z') -{ 1 }-> 2 :|: z' = X, X >= 0, z = 0
17.01/5.17	   a__first(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
17.01/5.17	   a__first(z, z') -{ 1 }-> 1 + Y + (1 + X + Z) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z
17.01/5.17	   a__from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X
17.01/5.17	   a__from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X
17.01/5.17	   a__if(z, z', z'') -{ 1 }-> mark(X) :|: z' = X, z = 3, Y >= 0, z'' = Y, X >= 0
17.01/5.17	   a__if(z, z', z'') -{ 1 }-> mark(Y) :|: z' = X, Y >= 0, z = 1, z'' = Y, X >= 0
17.01/5.17	   a__if(z, z', z'') -{ 1 }-> 1 + X1 + X2 + X3 :|: X1 >= 0, X3 >= 0, X2 >= 0, z = X1, z' = X2, z'' = X3
17.01/5.17	   mark(z) -{ 1 }-> a__if(mark(X1), X2, X3) :|: X1 >= 0, X3 >= 0, z = 1 + X1 + X2 + X3, X2 >= 0
17.01/5.17	   mark(z) -{ 1 }-> a__from(X) :|: z = 1 + X, X >= 0
17.01/5.17	   mark(z) -{ 1 }-> a__first(mark(X1), mark(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
17.01/5.17	   mark(z) -{ 1 }-> a__and(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
17.01/5.17	   mark(z) -{ 1 }-> a__add(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
17.01/5.17	   mark(z) -{ 1 }-> 3 :|: z = 3
17.01/5.17	   mark(z) -{ 1 }-> 2 :|: z = 2
17.01/5.17	   mark(z) -{ 1 }-> 1 :|: z = 1
17.01/5.17	   mark(z) -{ 1 }-> 0 :|: z = 0
17.01/5.17	   mark(z) -{ 1 }-> 1 + X :|: z = 1 + X, X >= 0
17.01/5.17	   mark(z) -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
17.01/5.17	
17.01/5.17	Only complete derivations are relevant for the runtime complexity.
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(11) CompleteCoflocoProof (FINISHED)
17.01/5.17	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
17.01/5.17	
17.01/5.17	eq(start(V1, V, V2),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]).
17.01/5.17	eq(start(V1, V, V2),0,[fun1(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
17.01/5.17	eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]).
17.01/5.17	eq(start(V1, V, V2),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]).
17.01/5.17	eq(start(V1, V, V2),0,[fun4(V1, Out)],[V1 >= 0]).
17.01/5.17	eq(start(V1, V, V2),0,[mark(V1, Out)],[V1 >= 0]).
17.01/5.17	eq(fun(V1, V, Out),1,[mark(X4, Ret)],[Out = Ret,V = X4,V1 = 3,X4 >= 0]).
17.01/5.17	eq(fun(V1, V, Out),1,[],[Out = 1,V = Y1,Y1 >= 0,V1 = 1]).
17.01/5.17	eq(fun1(V1, V, V2, Out),1,[mark(X5, Ret1)],[Out = Ret1,V = X5,V1 = 3,Y2 >= 0,V2 = Y2,X5 >= 0]).
17.01/5.17	eq(fun1(V1, V, V2, Out),1,[mark(Y3, Ret2)],[Out = Ret2,V = X6,Y3 >= 0,V1 = 1,V2 = Y3,X6 >= 0]).
17.01/5.17	eq(fun2(V1, V, Out),1,[mark(X7, Ret3)],[Out = Ret3,V = X7,X7 >= 0,V1 = 0]).
17.01/5.17	eq(fun2(V1, V, Out),1,[],[Out = 2 + X8 + Y4,V1 = 1 + X8,V = Y4,Y4 >= 0,X8 >= 0]).
17.01/5.17	eq(fun3(V1, V, Out),1,[],[Out = 2,V = X9,X9 >= 0,V1 = 0]).
17.01/5.17	eq(fun3(V1, V, Out),1,[],[Out = 2 + X10 + Y5 + Z1,Z1 >= 0,V1 = 1 + X10,Y5 >= 0,X10 >= 0,V = 1 + Y5 + Z1]).
17.01/5.17	eq(fun4(V1, Out),1,[],[Out = 3 + 2*X11,X11 >= 0,V1 = X11]).
17.01/5.17	eq(mark(V1, Out),1,[mark(X12, Ret0),fun(Ret0, X21, Ret4)],[Out = Ret4,X12 >= 0,X21 >= 0,V1 = 1 + X12 + X21]).
17.01/5.17	eq(mark(V1, Out),1,[mark(X13, Ret01),fun1(Ret01, X22, X31, Ret5)],[Out = Ret5,X13 >= 0,X31 >= 0,V1 = 1 + X13 + X22 + X31,X22 >= 0]).
17.01/5.17	eq(mark(V1, Out),1,[mark(X14, Ret02),fun2(Ret02, X23, Ret6)],[Out = Ret6,X14 >= 0,X23 >= 0,V1 = 1 + X14 + X23]).
17.01/5.17	eq(mark(V1, Out),1,[mark(X15, Ret03),mark(X24, Ret11),fun3(Ret03, Ret11, Ret7)],[Out = Ret7,X15 >= 0,X24 >= 0,V1 = 1 + X15 + X24]).
17.01/5.17	eq(mark(V1, Out),1,[fun4(X16, Ret8)],[Out = Ret8,V1 = 1 + X16,X16 >= 0]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 3,V1 = 3]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 1,V1 = 1]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 0,V1 = 0]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 1 + X17,V1 = 1 + X17,X17 >= 0]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 2,V1 = 2]).
17.01/5.17	eq(mark(V1, Out),1,[],[Out = 1 + X18 + X25,X18 >= 0,X25 >= 0,V1 = 1 + X18 + X25]).
17.01/5.17	eq(fun(V1, V, Out),1,[],[Out = 1 + X19 + X26,X19 >= 0,X26 >= 0,V1 = X19,V = X26]).
17.01/5.17	eq(fun1(V1, V, V2, Out),1,[],[Out = 1 + X110 + X27 + X32,X110 >= 0,X32 >= 0,X27 >= 0,V1 = X110,V = X27,V2 = X32]).
17.01/5.17	eq(fun2(V1, V, Out),1,[],[Out = 1 + X111 + X28,X111 >= 0,X28 >= 0,V1 = X111,V = X28]).
17.01/5.17	eq(fun3(V1, V, Out),1,[],[Out = 1 + X112 + X29,X112 >= 0,X29 >= 0,V1 = X112,V = X29]).
17.01/5.17	eq(fun4(V1, Out),1,[],[Out = 1 + X20,X20 >= 0,V1 = X20]).
17.01/5.17	input_output_vars(fun(V1,V,Out),[V1,V],[Out]).
17.01/5.17	input_output_vars(fun1(V1,V,V2,Out),[V1,V,V2],[Out]).
17.01/5.17	input_output_vars(fun2(V1,V,Out),[V1,V],[Out]).
17.01/5.17	input_output_vars(fun3(V1,V,Out),[V1,V],[Out]).
17.01/5.17	input_output_vars(fun4(V1,Out),[V1],[Out]).
17.01/5.17	input_output_vars(mark(V1,Out),[V1],[Out]).
17.01/5.17	
17.01/5.17	
17.01/5.17	CoFloCo proof output:
17.01/5.17	Preprocessing Cost Relations
17.01/5.17	=====================================
17.01/5.17	
17.01/5.17	#### Computed strongly connected components 
17.01/5.17	0. non_recursive  : [fun3/3]
17.01/5.17	1. non_recursive  : [fun4/2]
17.01/5.17	2. recursive [non_tail,multiple] : [fun/3,fun1/4,fun2/3,mark/2]
17.01/5.17	3. non_recursive  : [start/3]
17.01/5.17	
17.01/5.17	#### Obtained direct recursion through partial evaluation 
17.01/5.17	0. SCC is partially evaluated into fun3/3
17.01/5.17	1. SCC is partially evaluated into fun4/2
17.01/5.17	2. SCC is partially evaluated into mark/2
17.01/5.17	3. SCC is partially evaluated into start/3
17.01/5.17	
17.01/5.17	Control-Flow Refinement of Cost Relations
17.01/5.17	=====================================
17.01/5.17	
17.01/5.17	### Specialization of cost equations fun3/3 
17.01/5.17	* CE 19 is refined into CE [23] 
17.01/5.17	* CE 20 is refined into CE [24] 
17.01/5.17	* CE 18 is refined into CE [25] 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Cost equations --> "Loop" of fun3/3 
17.01/5.17	* CEs [23] --> Loop 16 
17.01/5.17	* CEs [24] --> Loop 17 
17.01/5.17	* CEs [25] --> Loop 18 
17.01/5.17	
17.01/5.17	### Ranking functions of CR fun3(V1,V,Out) 
17.01/5.17	
17.01/5.17	#### Partial ranking functions of CR fun3(V1,V,Out) 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Specialization of cost equations fun4/2 
17.01/5.17	* CE 21 is refined into CE [26] 
17.01/5.17	* CE 22 is refined into CE [27] 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Cost equations --> "Loop" of fun4/2 
17.01/5.17	* CEs [26] --> Loop 19 
17.01/5.17	* CEs [27] --> Loop 20 
17.01/5.17	
17.01/5.17	### Ranking functions of CR fun4(V1,Out) 
17.01/5.17	
17.01/5.17	#### Partial ranking functions of CR fun4(V1,Out) 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Specialization of cost equations mark/2 
17.01/5.17	* CE 14 is refined into CE [28,29] 
17.01/5.17	* CE 15 is refined into CE [30] 
17.01/5.17	* CE 16 is refined into CE [31] 
17.01/5.17	* CE 17 is refined into CE [32] 
17.01/5.17	* CE 11 is refined into CE [33] 
17.01/5.17	* CE 10 is refined into CE [34] 
17.01/5.17	* CE 9 is refined into CE [35] 
17.01/5.17	* CE 13 is refined into CE [36,37,38] 
17.01/5.17	* CE 8 is refined into CE [39] 
17.01/5.17	* CE 12 is refined into CE [40] 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Cost equations --> "Loop" of mark/2 
17.01/5.17	* CEs [39] --> Loop 21 
17.01/5.17	* CEs [40] --> Loop 22 
17.01/5.17	* CEs [38] --> Loop 23 
17.01/5.17	* CEs [37] --> Loop 24 
17.01/5.17	* CEs [33] --> Loop 25 
17.01/5.17	* CEs [34] --> Loop 26 
17.01/5.17	* CEs [35] --> Loop 27 
17.01/5.17	* CEs [36] --> Loop 28 
17.01/5.17	* CEs [29] --> Loop 29 
17.01/5.17	* CEs [28,30,31] --> Loop 30 
17.01/5.17	* CEs [32] --> Loop 31 
17.01/5.17	
17.01/5.17	### Ranking functions of CR mark(V1,Out) 
17.01/5.17	* RF of phase [21,22,23,24,25,26,27,28]: [V1]
17.01/5.17	
17.01/5.17	#### Partial ranking functions of CR mark(V1,Out) 
17.01/5.17	* Partial RF of phase [21,22,23,24,25,26,27,28]:
17.01/5.17	  - RF of loop [21:1,22:1,23:1,23:2,24:1,24:2,25:1,25:2,26:1,26:2,27:1,27:2,28:1,28:2]:
17.01/5.17	    V1
17.01/5.17	
17.01/5.17	
17.01/5.17	### Specialization of cost equations start/3 
17.01/5.17	* CE 4 is refined into CE [41,42,43] 
17.01/5.17	* CE 3 is refined into CE [44,45,46] 
17.01/5.17	* CE 1 is refined into CE [47] 
17.01/5.17	* CE 2 is refined into CE [48,49,50] 
17.01/5.17	* CE 5 is refined into CE [51,52,53] 
17.01/5.17	* CE 6 is refined into CE [54,55] 
17.01/5.17	* CE 7 is refined into CE [56,57,58] 
17.01/5.17	
17.01/5.17	
17.01/5.17	### Cost equations --> "Loop" of start/3 
17.01/5.17	* CEs [42,43] --> Loop 32 
17.01/5.17	* CEs [41] --> Loop 33 
17.01/5.17	* CEs [45,46] --> Loop 34 
17.01/5.17	* CEs [44] --> Loop 35 
17.01/5.17	* CEs [47,48,49,50,51,52,53,54,55,56,57,58] --> Loop 36 
17.01/5.17	
17.01/5.17	### Ranking functions of CR start(V1,V,V2) 
17.01/5.17	
17.01/5.17	#### Partial ranking functions of CR start(V1,V,V2) 
17.01/5.17	
17.01/5.17	
17.01/5.17	Computing Bounds
17.01/5.17	=====================================
17.01/5.17	
17.01/5.17	#### Cost of chains of fun3(V1,V,Out):
17.01/5.17	* Chain [18]: 1
17.01/5.17	  with precondition: [V1=0,Out=2,V>=0] 
17.01/5.17	
17.01/5.17	* Chain [17]: 1
17.01/5.17	  with precondition: [V+V1+1=Out,V1>=0,V>=0] 
17.01/5.17	
17.01/5.17	* Chain [16]: 1
17.01/5.17	  with precondition: [V+V1=Out,V1>=1,V>=1] 
17.01/5.17	
17.01/5.17	
17.01/5.17	#### Cost of chains of fun4(V1,Out):
17.01/5.17	* Chain [20]: 1
17.01/5.17	  with precondition: [V1+1=Out,V1>=0] 
17.01/5.17	
17.01/5.17	* Chain [19]: 1
17.01/5.17	  with precondition: [2*V1+3=Out,V1>=0] 
17.01/5.17	
17.01/5.17	
17.01/5.17	#### Cost of chains of mark(V1,Out):
17.01/5.17	* Chain [31]: 1
17.01/5.17	  with precondition: [V1=0,Out=0] 
17.01/5.17	
17.01/5.17	* Chain [30]: 2
17.01/5.17	  with precondition: [V1=Out,V1>=1] 
17.01/5.17	
17.01/5.17	* Chain [29]: 2
17.01/5.17	  with precondition: [2*V1+1=Out,V1>=1] 
17.01/5.17	
17.01/5.17	* Chain [multiple([21,22,23,24,25,26,27,28],[[31],[30],[29]])]: 4*it(21)+2*it(23)+6*it(24)+2*it(25)+2*it(26)+4*it([29])+1*it([31])+0
17.01/5.17	  Such that:aux(10) =< 1
17.01/5.17	aux(11) =< V1
17.01/5.17	aux(12) =< 2/3*V1
17.01/5.17	aux(13) =< 4/3*V1+1/3
17.01/5.17	aux(14) =< 6/7*V1
17.01/5.17	it(21) =< aux(11)
17.01/5.17	it(23) =< aux(11)
17.01/5.17	it(24) =< aux(11)
17.01/5.17	it(25) =< aux(11)
17.01/5.17	it(26) =< aux(11)
17.01/5.17	it([29]) =< aux(11)
17.01/5.17	it(25) =< aux(12)
17.01/5.17	it(24) =< aux(13)
17.01/5.17	it(25) =< aux(13)
17.01/5.17	it(26) =< aux(13)
17.01/5.17	it([29]) =< aux(13)
17.01/5.17	it(23) =< aux(14)
17.01/5.17	it(25) =< aux(14)
17.01/5.17	it(26) =< aux(14)
17.01/5.17	it([29]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10)
17.01/5.17	it([31]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10)
17.01/5.17	
17.01/5.17	  with precondition: [V1>=1,Out>=0,5*V1>=2*Out+1,2*V1+1>=Out] 
17.01/5.17	
17.01/5.17	
17.01/5.17	#### Cost of chains of start(V1,V,V2):
17.01/5.17	* Chain [36]: 4*s(18)+2*s(19)+6*s(20)+2*s(21)+2*s(22)+4*s(23)+1*s(24)+4*s(30)+2*s(31)+6*s(32)+2*s(33)+2*s(34)+4*s(35)+1*s(36)+3
17.01/5.17	  Such that:s(26) =< V1
17.01/5.17	s(27) =< 2/3*V1
17.01/5.17	s(28) =< 4/3*V1+1/3
17.01/5.17	s(29) =< 6/7*V1
17.01/5.17	s(14) =< V
17.01/5.17	s(15) =< 2/3*V
17.01/5.17	s(16) =< 4/3*V+1/3
17.01/5.17	s(17) =< 6/7*V
17.01/5.17	aux(15) =< 1
17.01/5.17	s(18) =< s(14)
17.01/5.17	s(19) =< s(14)
17.01/5.17	s(20) =< s(14)
17.01/5.17	s(21) =< s(14)
17.01/5.17	s(22) =< s(14)
17.01/5.17	s(23) =< s(14)
17.01/5.17	s(21) =< s(15)
17.01/5.17	s(20) =< s(16)
17.01/5.17	s(21) =< s(16)
17.01/5.17	s(22) =< s(16)
17.01/5.17	s(23) =< s(16)
17.01/5.17	s(19) =< s(17)
17.01/5.17	s(21) =< s(17)
17.01/5.17	s(22) =< s(17)
17.01/5.17	s(23) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15)
17.01/5.17	s(24) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15)
17.01/5.17	s(30) =< s(26)
17.01/5.17	s(31) =< s(26)
17.01/5.17	s(32) =< s(26)
17.01/5.17	s(33) =< s(26)
17.01/5.17	s(34) =< s(26)
17.01/5.17	s(35) =< s(26)
17.01/5.17	s(33) =< s(27)
17.01/5.17	s(32) =< s(28)
17.01/5.17	s(33) =< s(28)
17.01/5.17	s(34) =< s(28)
17.01/5.17	s(35) =< s(28)
17.01/5.17	s(31) =< s(29)
17.01/5.17	s(33) =< s(29)
17.01/5.17	s(34) =< s(29)
17.01/5.17	s(35) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15)
17.01/5.17	s(36) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15)
17.01/5.17	
17.01/5.17	  with precondition: [V1>=0] 
17.01/5.17	
17.01/5.17	* Chain [35]: 2
17.01/5.17	  with precondition: [V1=1,V2=0,V>=0] 
17.01/5.17	
17.01/5.17	* Chain [34]: 4*s(42)+2*s(43)+6*s(44)+2*s(45)+2*s(46)+4*s(47)+1*s(48)+3
17.01/5.17	  Such that:s(37) =< 1
17.01/5.17	s(38) =< V2
17.01/5.17	s(39) =< 2/3*V2
17.01/5.17	s(40) =< 4/3*V2+1/3
17.01/5.17	s(41) =< 6/7*V2
17.01/5.17	s(42) =< s(38)
17.01/5.17	s(43) =< s(38)
17.01/5.17	s(44) =< s(38)
17.01/5.17	s(45) =< s(38)
17.01/5.17	s(46) =< s(38)
17.01/5.17	s(47) =< s(38)
17.01/5.17	s(45) =< s(39)
17.01/5.17	s(44) =< s(40)
17.01/5.17	s(45) =< s(40)
17.01/5.17	s(46) =< s(40)
17.01/5.17	s(47) =< s(40)
17.01/5.17	s(43) =< s(41)
17.01/5.17	s(45) =< s(41)
17.01/5.17	s(46) =< s(41)
17.01/5.17	s(47) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37)
17.01/5.17	s(48) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37)
17.01/5.17	
17.01/5.17	  with precondition: [V1=1,V>=0,V2>=1] 
17.01/5.17	
17.01/5.17	* Chain [33]: 2
17.01/5.17	  with precondition: [V1=3,V=0] 
17.01/5.17	
17.01/5.17	* Chain [32]: 4*s(54)+2*s(55)+6*s(56)+2*s(57)+2*s(58)+4*s(59)+1*s(60)+3
17.01/5.17	  Such that:s(49) =< 1
17.01/5.17	s(50) =< V
17.01/5.17	s(51) =< 2/3*V
17.01/5.17	s(52) =< 4/3*V+1/3
17.01/5.17	s(53) =< 6/7*V
17.01/5.17	s(54) =< s(50)
17.01/5.17	s(55) =< s(50)
17.01/5.17	s(56) =< s(50)
17.01/5.17	s(57) =< s(50)
17.01/5.17	s(58) =< s(50)
17.01/5.17	s(59) =< s(50)
17.01/5.17	s(57) =< s(51)
17.01/5.17	s(56) =< s(52)
17.01/5.17	s(57) =< s(52)
17.01/5.17	s(58) =< s(52)
17.01/5.17	s(59) =< s(52)
17.01/5.17	s(55) =< s(53)
17.01/5.17	s(57) =< s(53)
17.01/5.17	s(58) =< s(53)
17.01/5.17	s(59) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49)
17.01/5.17	s(60) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49)
17.01/5.17	
17.01/5.17	  with precondition: [V1=3,V>=1] 
17.01/5.17	
17.01/5.17	
17.01/5.17	Closed-form bounds of start(V1,V,V2): 
17.01/5.17	-------------------------------------
17.01/5.17	* Chain [36] with precondition: [V1>=0] 
17.01/5.17	    - Upper bound: 26*V1+5+nat(V)*26 
17.01/5.17	    - Complexity: n 
17.01/5.17	* Chain [35] with precondition: [V1=1,V2=0,V>=0] 
17.01/5.17	    - Upper bound: 2 
17.01/5.17	    - Complexity: constant 
17.01/5.17	* Chain [34] with precondition: [V1=1,V>=0,V2>=1] 
17.01/5.17	    - Upper bound: 26*V2+4 
17.01/5.17	    - Complexity: n 
17.01/5.17	* Chain [33] with precondition: [V1=3,V=0] 
17.01/5.17	    - Upper bound: 2 
17.01/5.17	    - Complexity: constant 
17.01/5.17	* Chain [32] with precondition: [V1=3,V>=1] 
17.01/5.17	    - Upper bound: 26*V+4 
17.01/5.17	    - Complexity: n 
17.01/5.17	
17.01/5.17	### Maximum cost of start(V1,V,V2): max([nat(V2)*26+2,nat(V)*26+2+(26*V1+1)])+2 
17.01/5.17	Asymptotic class: n 
17.01/5.17	* Total analysis performed in 381 ms.
17.01/5.17	
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(12)
17.01/5.17	BOUNDS(1, n^1)
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
17.01/5.17	Transformed a relative TRS into a decreasing-loop problem.
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(14)
17.01/5.17	Obligation:
17.01/5.17	Analyzing the following TRS for decreasing loops:
17.01/5.17	
17.01/5.17	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X)
17.01/5.17	   a__and(false, Y) -> false
17.01/5.17	   a__if(true, X, Y) -> mark(X)
17.01/5.17	   a__if(false, X, Y) -> mark(Y)
17.01/5.17	   a__add(0, X) -> mark(X)
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y))
17.01/5.17	   a__first(0, X) -> nil
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
17.01/5.17	   a__from(X) -> cons(X, from(s(X)))
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
17.01/5.17	   mark(from(X)) -> a__from(X)
17.01/5.17	   mark(true) -> true
17.01/5.17	   mark(false) -> false
17.01/5.17	   mark(0) -> 0
17.01/5.17	   mark(s(X)) -> s(X)
17.01/5.17	   mark(nil) -> nil
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2)
17.01/5.17	   a__and(X1, X2) -> and(X1, X2)
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3)
17.01/5.17	   a__add(X1, X2) -> add(X1, X2)
17.01/5.17	   a__first(X1, X2) -> first(X1, X2)
17.01/5.17	   a__from(X) -> from(X)
17.01/5.17	
17.01/5.17	S is empty.
17.01/5.17	Rewrite Strategy: FULL
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(15) DecreasingLoopProof (LOWER BOUND(ID))
17.01/5.17	The following loop(s) give(s) rise to the lower bound Omega(n^1):
17.01/5.17	
17.01/5.17	The rewrite sequence
17.01/5.17	
17.01/5.17	mark(and(X1, X2)) ->^+ a__and(mark(X1), X2)
17.01/5.17	
17.01/5.17	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
17.01/5.17	
17.01/5.17	The pumping substitution is [X1 / and(X1, X2)].
17.01/5.17	
17.01/5.17	The result substitution is [ ].
17.01/5.17	
17.01/5.17	
17.01/5.17	
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(16)
17.01/5.17	Complex Obligation (BEST)
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(17)
17.01/5.17	Obligation:
17.01/5.17	Proved the lower bound n^1 for the following obligation:
17.01/5.17	
17.01/5.17	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X)
17.01/5.17	   a__and(false, Y) -> false
17.01/5.17	   a__if(true, X, Y) -> mark(X)
17.01/5.17	   a__if(false, X, Y) -> mark(Y)
17.01/5.17	   a__add(0, X) -> mark(X)
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y))
17.01/5.17	   a__first(0, X) -> nil
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
17.01/5.17	   a__from(X) -> cons(X, from(s(X)))
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
17.01/5.17	   mark(from(X)) -> a__from(X)
17.01/5.17	   mark(true) -> true
17.01/5.17	   mark(false) -> false
17.01/5.17	   mark(0) -> 0
17.01/5.17	   mark(s(X)) -> s(X)
17.01/5.17	   mark(nil) -> nil
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2)
17.01/5.17	   a__and(X1, X2) -> and(X1, X2)
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3)
17.01/5.17	   a__add(X1, X2) -> add(X1, X2)
17.01/5.17	   a__first(X1, X2) -> first(X1, X2)
17.01/5.17	   a__from(X) -> from(X)
17.01/5.17	
17.01/5.17	S is empty.
17.01/5.17	Rewrite Strategy: FULL
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(18) LowerBoundPropagationProof (FINISHED)
17.01/5.17	Propagated lower bound.
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(19)
17.01/5.17	BOUNDS(n^1, INF)
17.01/5.17	
17.01/5.17	----------------------------------------
17.01/5.17	
17.01/5.17	(20)
17.01/5.17	Obligation:
17.01/5.17	Analyzing the following TRS for decreasing loops:
17.01/5.17	
17.01/5.17	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.01/5.17	
17.01/5.17	
17.01/5.17	The TRS R consists of the following rules:
17.01/5.17	
17.01/5.17	   a__and(true, X) -> mark(X)
17.01/5.17	   a__and(false, Y) -> false
17.01/5.17	   a__if(true, X, Y) -> mark(X)
17.01/5.17	   a__if(false, X, Y) -> mark(Y)
17.01/5.17	   a__add(0, X) -> mark(X)
17.01/5.17	   a__add(s(X), Y) -> s(add(X, Y))
17.01/5.17	   a__first(0, X) -> nil
17.01/5.17	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
17.01/5.17	   a__from(X) -> cons(X, from(s(X)))
17.01/5.17	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
17.01/5.17	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
17.01/5.17	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
17.01/5.17	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
17.01/5.17	   mark(from(X)) -> a__from(X)
17.01/5.17	   mark(true) -> true
17.01/5.17	   mark(false) -> false
17.01/5.17	   mark(0) -> 0
17.01/5.17	   mark(s(X)) -> s(X)
17.01/5.17	   mark(nil) -> nil
17.01/5.17	   mark(cons(X1, X2)) -> cons(X1, X2)
17.01/5.17	   a__and(X1, X2) -> and(X1, X2)
17.01/5.17	   a__if(X1, X2, X3) -> if(X1, X2, X3)
17.01/5.17	   a__add(X1, X2) -> add(X1, X2)
17.01/5.17	   a__first(X1, X2) -> first(X1, X2)
17.01/5.17	   a__from(X) -> from(X)
17.01/5.17	
17.01/5.17	S is empty.
17.01/5.17	Rewrite Strategy: FULL
17.30/5.22	EOF