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