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