14.18/4.49	WORST_CASE(Omega(n^1), O(n^1))
14.18/4.51	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
14.18/4.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.18/4.51	
14.18/4.51	
14.18/4.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.18/4.51	
14.18/4.51	(0) CpxTRS
14.18/4.51	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
14.18/4.51	(2) CdtProblem
14.18/4.51	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
14.18/4.51	    (4) CdtProblem
14.18/4.51	    (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
14.18/4.51	    (6) CdtProblem
14.18/4.51	    (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
14.18/4.51	    (8) CdtProblem
14.18/4.51	    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
14.18/4.51	    (10) CdtProblem
14.18/4.51	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 55 ms]
14.18/4.51	    (12) CdtProblem
14.18/4.51	    (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
14.18/4.51	    (14) BOUNDS(1, 1)
14.18/4.51	(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
14.18/4.51	(16) TRS for Loop Detection
14.18/4.51	    (17) DecreasingLoopProof [LOWER BOUND(ID), 25 ms]
14.18/4.51	    (18) BEST
14.18/4.51	        (19) proven lower bound
14.18/4.51	            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
14.18/4.51	            (21) BOUNDS(n^1, INF)
14.18/4.51	        (22) TRS for Loop Detection
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(0)
14.18/4.51	Obligation:
14.18/4.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.18/4.51	
14.18/4.51	
14.18/4.51	The TRS R consists of the following rules:
14.18/4.51	
14.18/4.51	   natsFrom(N) -> cons(N, n__natsFrom(s(N)))
14.18/4.51	   fst(pair(XS, YS)) -> XS
14.18/4.51	   snd(pair(XS, YS)) -> YS
14.18/4.51	   splitAt(0, XS) -> pair(nil, XS)
14.18/4.51	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS))
14.18/4.51	   u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS)
14.18/4.51	   head(cons(N, XS)) -> N
14.18/4.51	   tail(cons(N, XS)) -> activate(XS)
14.18/4.51	   sel(N, XS) -> head(afterNth(N, XS))
14.18/4.51	   take(N, XS) -> fst(splitAt(N, XS))
14.18/4.51	   afterNth(N, XS) -> snd(splitAt(N, XS))
14.18/4.51	   natsFrom(X) -> n__natsFrom(X)
14.18/4.51	   activate(n__natsFrom(X)) -> natsFrom(X)
14.18/4.51	   activate(X) -> X
14.18/4.51	
14.18/4.51	S is empty.
14.18/4.51	Rewrite Strategy: INNERMOST
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
14.18/4.51	Converted Cpx (relative) TRS to CDT
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(2)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	   fst(pair(z0, z1)) -> z0
14.18/4.51	   snd(pair(z0, z1)) -> z1
14.18/4.51	   splitAt(0, z0) -> pair(nil, z0)
14.18/4.51	   splitAt(s(z0), cons(z1, z2)) -> u(splitAt(z0, activate(z2)), z0, z1, activate(z2))
14.18/4.51	   u(pair(z0, z1), z2, z3, z4) -> pair(cons(activate(z3), z0), z1)
14.18/4.51	   head(cons(z0, z1)) -> z0
14.18/4.51	   tail(cons(z0, z1)) -> activate(z1)
14.18/4.51	   sel(z0, z1) -> head(afterNth(z0, z1))
14.18/4.51	   take(z0, z1) -> fst(splitAt(z0, z1))
14.18/4.51	   afterNth(z0, z1) -> snd(splitAt(z0, z1))
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	Tuples:
14.18/4.51	   NATSFROM(z0) -> c
14.18/4.51	   NATSFROM(z0) -> c1
14.18/4.51	   FST(pair(z0, z1)) -> c2
14.18/4.51	   SND(pair(z0, z1)) -> c3
14.18/4.51	   SPLITAT(0, z0) -> c4
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(U(splitAt(z0, activate(z2)), z0, z1, activate(z2)), SPLITAT(z0, activate(z2)), ACTIVATE(z2), ACTIVATE(z2))
14.18/4.51	   U(pair(z0, z1), z2, z3, z4) -> c6(ACTIVATE(z3))
14.18/4.51	   HEAD(cons(z0, z1)) -> c7
14.18/4.51	   TAIL(cons(z0, z1)) -> c8(ACTIVATE(z1))
14.18/4.51	   SEL(z0, z1) -> c9(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(FST(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SND(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   ACTIVATE(n__natsFrom(z0)) -> c12(NATSFROM(z0))
14.18/4.51	   ACTIVATE(z0) -> c13
14.18/4.51	S tuples:
14.18/4.51	   NATSFROM(z0) -> c
14.18/4.51	   NATSFROM(z0) -> c1
14.18/4.51	   FST(pair(z0, z1)) -> c2
14.18/4.51	   SND(pair(z0, z1)) -> c3
14.18/4.51	   SPLITAT(0, z0) -> c4
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(U(splitAt(z0, activate(z2)), z0, z1, activate(z2)), SPLITAT(z0, activate(z2)), ACTIVATE(z2), ACTIVATE(z2))
14.18/4.51	   U(pair(z0, z1), z2, z3, z4) -> c6(ACTIVATE(z3))
14.18/4.51	   HEAD(cons(z0, z1)) -> c7
14.18/4.51	   TAIL(cons(z0, z1)) -> c8(ACTIVATE(z1))
14.18/4.51	   SEL(z0, z1) -> c9(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(FST(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SND(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   ACTIVATE(n__natsFrom(z0)) -> c12(NATSFROM(z0))
14.18/4.51	   ACTIVATE(z0) -> c13
14.18/4.51	K tuples:none
14.18/4.51	Defined Rule Symbols:   natsFrom_1, fst_1, snd_1, splitAt_2, u_4, head_1, tail_1, sel_2, take_2, afterNth_2, activate_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   NATSFROM_1, FST_1, SND_1, SPLITAT_2, U_4, HEAD_1, TAIL_1, SEL_2, TAKE_2, AFTERNTH_2, ACTIVATE_1
14.18/4.51	
14.18/4.51	Compound Symbols:   c, c1, c2, c3, c4, c5_4, c6_1, c7, c8_1, c9_2, c10_2, c11_2, c12_1, c13
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
14.18/4.51	Removed 10 trailing nodes:
14.18/4.51	   FST(pair(z0, z1)) -> c2
14.18/4.51	   U(pair(z0, z1), z2, z3, z4) -> c6(ACTIVATE(z3))
14.18/4.51	   ACTIVATE(n__natsFrom(z0)) -> c12(NATSFROM(z0))
14.18/4.51	   HEAD(cons(z0, z1)) -> c7
14.18/4.51	   NATSFROM(z0) -> c
14.18/4.51	   ACTIVATE(z0) -> c13
14.18/4.51	   SND(pair(z0, z1)) -> c3
14.18/4.51	   NATSFROM(z0) -> c1
14.18/4.51	   SPLITAT(0, z0) -> c4
14.18/4.51	   TAIL(cons(z0, z1)) -> c8(ACTIVATE(z1))
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(4)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	   fst(pair(z0, z1)) -> z0
14.18/4.51	   snd(pair(z0, z1)) -> z1
14.18/4.51	   splitAt(0, z0) -> pair(nil, z0)
14.18/4.51	   splitAt(s(z0), cons(z1, z2)) -> u(splitAt(z0, activate(z2)), z0, z1, activate(z2))
14.18/4.51	   u(pair(z0, z1), z2, z3, z4) -> pair(cons(activate(z3), z0), z1)
14.18/4.51	   head(cons(z0, z1)) -> z0
14.18/4.51	   tail(cons(z0, z1)) -> activate(z1)
14.18/4.51	   sel(z0, z1) -> head(afterNth(z0, z1))
14.18/4.51	   take(z0, z1) -> fst(splitAt(z0, z1))
14.18/4.51	   afterNth(z0, z1) -> snd(splitAt(z0, z1))
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(U(splitAt(z0, activate(z2)), z0, z1, activate(z2)), SPLITAT(z0, activate(z2)), ACTIVATE(z2), ACTIVATE(z2))
14.18/4.51	   SEL(z0, z1) -> c9(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(FST(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SND(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	S tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(U(splitAt(z0, activate(z2)), z0, z1, activate(z2)), SPLITAT(z0, activate(z2)), ACTIVATE(z2), ACTIVATE(z2))
14.18/4.51	   SEL(z0, z1) -> c9(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(FST(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SND(splitAt(z0, z1)), SPLITAT(z0, z1))
14.18/4.51	K tuples:none
14.18/4.51	Defined Rule Symbols:   natsFrom_1, fst_1, snd_1, splitAt_2, u_4, head_1, tail_1, sel_2, take_2, afterNth_2, activate_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   SPLITAT_2, SEL_2, TAKE_2, AFTERNTH_2
14.18/4.51	
14.18/4.51	Compound Symbols:   c5_4, c9_2, c10_2, c11_2
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
14.18/4.51	Removed 6 trailing tuple parts
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(6)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	   fst(pair(z0, z1)) -> z0
14.18/4.51	   snd(pair(z0, z1)) -> z1
14.18/4.51	   splitAt(0, z0) -> pair(nil, z0)
14.18/4.51	   splitAt(s(z0), cons(z1, z2)) -> u(splitAt(z0, activate(z2)), z0, z1, activate(z2))
14.18/4.51	   u(pair(z0, z1), z2, z3, z4) -> pair(cons(activate(z3), z0), z1)
14.18/4.51	   head(cons(z0, z1)) -> z0
14.18/4.51	   tail(cons(z0, z1)) -> activate(z1)
14.18/4.51	   sel(z0, z1) -> head(afterNth(z0, z1))
14.18/4.51	   take(z0, z1) -> fst(splitAt(z0, z1))
14.18/4.51	   afterNth(z0, z1) -> snd(splitAt(z0, z1))
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	   SEL(z0, z1) -> c9(AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SPLITAT(z0, z1))
14.18/4.51	S tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	   SEL(z0, z1) -> c9(AFTERNTH(z0, z1))
14.18/4.51	   TAKE(z0, z1) -> c10(SPLITAT(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SPLITAT(z0, z1))
14.18/4.51	K tuples:none
14.18/4.51	Defined Rule Symbols:   natsFrom_1, fst_1, snd_1, splitAt_2, u_4, head_1, tail_1, sel_2, take_2, afterNth_2, activate_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   SPLITAT_2, SEL_2, TAKE_2, AFTERNTH_2
14.18/4.51	
14.18/4.51	Compound Symbols:   c5_1, c9_1, c10_1, c11_1
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(7) CdtLeafRemovalProof (ComplexityIfPolyImplication)
14.18/4.51	Removed 3 leading nodes:
14.18/4.51	   TAKE(z0, z1) -> c10(SPLITAT(z0, z1))
14.18/4.51	   SEL(z0, z1) -> c9(AFTERNTH(z0, z1))
14.18/4.51	   AFTERNTH(z0, z1) -> c11(SPLITAT(z0, z1))
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(8)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	   fst(pair(z0, z1)) -> z0
14.18/4.51	   snd(pair(z0, z1)) -> z1
14.18/4.51	   splitAt(0, z0) -> pair(nil, z0)
14.18/4.51	   splitAt(s(z0), cons(z1, z2)) -> u(splitAt(z0, activate(z2)), z0, z1, activate(z2))
14.18/4.51	   u(pair(z0, z1), z2, z3, z4) -> pair(cons(activate(z3), z0), z1)
14.18/4.51	   head(cons(z0, z1)) -> z0
14.18/4.51	   tail(cons(z0, z1)) -> activate(z1)
14.18/4.51	   sel(z0, z1) -> head(afterNth(z0, z1))
14.18/4.51	   take(z0, z1) -> fst(splitAt(z0, z1))
14.18/4.51	   afterNth(z0, z1) -> snd(splitAt(z0, z1))
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	S tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	K tuples:none
14.18/4.51	Defined Rule Symbols:   natsFrom_1, fst_1, snd_1, splitAt_2, u_4, head_1, tail_1, sel_2, take_2, afterNth_2, activate_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   SPLITAT_2
14.18/4.51	
14.18/4.51	Compound Symbols:   c5_1
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
14.18/4.51	The following rules are not usable and were removed:
14.18/4.51	   fst(pair(z0, z1)) -> z0
14.18/4.51	   snd(pair(z0, z1)) -> z1
14.18/4.51	   splitAt(0, z0) -> pair(nil, z0)
14.18/4.51	   splitAt(s(z0), cons(z1, z2)) -> u(splitAt(z0, activate(z2)), z0, z1, activate(z2))
14.18/4.51	   u(pair(z0, z1), z2, z3, z4) -> pair(cons(activate(z3), z0), z1)
14.18/4.51	   head(cons(z0, z1)) -> z0
14.18/4.51	   tail(cons(z0, z1)) -> activate(z1)
14.18/4.51	   sel(z0, z1) -> head(afterNth(z0, z1))
14.18/4.51	   take(z0, z1) -> fst(splitAt(z0, z1))
14.18/4.51	   afterNth(z0, z1) -> snd(splitAt(z0, z1))
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(10)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	S tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	K tuples:none
14.18/4.51	Defined Rule Symbols:   activate_1, natsFrom_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   SPLITAT_2
14.18/4.51	
14.18/4.51	Compound Symbols:   c5_1
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
14.18/4.51	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	We considered the (Usable) Rules:
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	And the Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	The order we found is given by the following interpretation:
14.18/4.51	
14.18/4.51	Polynomial interpretation :
14.18/4.51	
14.18/4.51	   POL(SPLITAT(x_1, x_2)) = x_1 + x_2
14.18/4.51	   POL(activate(x_1)) = x_1
14.18/4.51	   POL(c5(x_1)) = x_1
14.18/4.51	   POL(cons(x_1, x_2)) = x_2
14.18/4.51	   POL(n__natsFrom(x_1)) = [1]
14.18/4.51	   POL(natsFrom(x_1)) = [1]
14.18/4.51	   POL(s(x_1)) = [1] + x_1
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(12)
14.18/4.51	Obligation:
14.18/4.51	Complexity Dependency Tuples Problem
14.18/4.51	
14.18/4.51	Rules:
14.18/4.51	   activate(n__natsFrom(z0)) -> natsFrom(z0)
14.18/4.51	   activate(z0) -> z0
14.18/4.51	   natsFrom(z0) -> cons(z0, n__natsFrom(s(z0)))
14.18/4.51	   natsFrom(z0) -> n__natsFrom(z0)
14.18/4.51	Tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	S tuples:none
14.18/4.51	K tuples:
14.18/4.51	   SPLITAT(s(z0), cons(z1, z2)) -> c5(SPLITAT(z0, activate(z2)))
14.18/4.51	Defined Rule Symbols:   activate_1, natsFrom_1
14.18/4.51	
14.18/4.51	Defined Pair Symbols:   SPLITAT_2
14.18/4.51	
14.18/4.51	Compound Symbols:   c5_1
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(13) SIsEmptyProof (BOTH BOUNDS(ID, ID))
14.18/4.51	The set S is empty
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(14)
14.18/4.51	BOUNDS(1, 1)
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
14.18/4.51	Transformed a relative TRS into a decreasing-loop problem.
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(16)
14.18/4.51	Obligation:
14.18/4.51	Analyzing the following TRS for decreasing loops:
14.18/4.51	
14.18/4.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.18/4.51	
14.18/4.51	
14.18/4.51	The TRS R consists of the following rules:
14.18/4.51	
14.18/4.51	   natsFrom(N) -> cons(N, n__natsFrom(s(N)))
14.18/4.51	   fst(pair(XS, YS)) -> XS
14.18/4.51	   snd(pair(XS, YS)) -> YS
14.18/4.51	   splitAt(0, XS) -> pair(nil, XS)
14.18/4.51	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS))
14.18/4.51	   u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS)
14.18/4.51	   head(cons(N, XS)) -> N
14.18/4.51	   tail(cons(N, XS)) -> activate(XS)
14.18/4.51	   sel(N, XS) -> head(afterNth(N, XS))
14.18/4.51	   take(N, XS) -> fst(splitAt(N, XS))
14.18/4.51	   afterNth(N, XS) -> snd(splitAt(N, XS))
14.18/4.51	   natsFrom(X) -> n__natsFrom(X)
14.18/4.51	   activate(n__natsFrom(X)) -> natsFrom(X)
14.18/4.51	   activate(X) -> X
14.18/4.51	
14.18/4.51	S is empty.
14.18/4.51	Rewrite Strategy: INNERMOST
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(17) DecreasingLoopProof (LOWER BOUND(ID))
14.18/4.51	The following loop(s) give(s) rise to the lower bound Omega(n^1):
14.18/4.51	
14.18/4.51	The rewrite sequence
14.18/4.51	
14.18/4.51	splitAt(s(N), cons(X, XS)) ->^+ u(splitAt(N, XS), N, X, activate(XS))
14.18/4.51	
14.18/4.51	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
14.18/4.51	
14.18/4.51	The pumping substitution is [N / s(N), XS / cons(X, XS)].
14.18/4.51	
14.18/4.51	The result substitution is [ ].
14.18/4.51	
14.18/4.51	
14.18/4.51	
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(18)
14.18/4.51	Complex Obligation (BEST)
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(19)
14.18/4.51	Obligation:
14.18/4.51	Proved the lower bound n^1 for the following obligation:
14.18/4.51	
14.18/4.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.18/4.51	
14.18/4.51	
14.18/4.51	The TRS R consists of the following rules:
14.18/4.51	
14.18/4.51	   natsFrom(N) -> cons(N, n__natsFrom(s(N)))
14.18/4.51	   fst(pair(XS, YS)) -> XS
14.18/4.51	   snd(pair(XS, YS)) -> YS
14.18/4.51	   splitAt(0, XS) -> pair(nil, XS)
14.18/4.51	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS))
14.18/4.51	   u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS)
14.18/4.51	   head(cons(N, XS)) -> N
14.18/4.51	   tail(cons(N, XS)) -> activate(XS)
14.18/4.51	   sel(N, XS) -> head(afterNth(N, XS))
14.18/4.51	   take(N, XS) -> fst(splitAt(N, XS))
14.18/4.51	   afterNth(N, XS) -> snd(splitAt(N, XS))
14.18/4.51	   natsFrom(X) -> n__natsFrom(X)
14.18/4.51	   activate(n__natsFrom(X)) -> natsFrom(X)
14.18/4.51	   activate(X) -> X
14.18/4.51	
14.18/4.51	S is empty.
14.18/4.51	Rewrite Strategy: INNERMOST
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(20) LowerBoundPropagationProof (FINISHED)
14.18/4.51	Propagated lower bound.
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(21)
14.18/4.51	BOUNDS(n^1, INF)
14.18/4.51	
14.18/4.51	----------------------------------------
14.18/4.51	
14.18/4.51	(22)
14.18/4.51	Obligation:
14.18/4.51	Analyzing the following TRS for decreasing loops:
14.18/4.51	
14.18/4.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.18/4.51	
14.18/4.51	
14.18/4.51	The TRS R consists of the following rules:
14.18/4.51	
14.18/4.51	   natsFrom(N) -> cons(N, n__natsFrom(s(N)))
14.18/4.51	   fst(pair(XS, YS)) -> XS
14.18/4.51	   snd(pair(XS, YS)) -> YS
14.18/4.51	   splitAt(0, XS) -> pair(nil, XS)
14.18/4.51	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS))
14.18/4.51	   u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS)
14.18/4.51	   head(cons(N, XS)) -> N
14.18/4.51	   tail(cons(N, XS)) -> activate(XS)
14.18/4.51	   sel(N, XS) -> head(afterNth(N, XS))
14.18/4.51	   take(N, XS) -> fst(splitAt(N, XS))
14.18/4.51	   afterNth(N, XS) -> snd(splitAt(N, XS))
14.18/4.51	   natsFrom(X) -> n__natsFrom(X)
14.18/4.51	   activate(n__natsFrom(X)) -> natsFrom(X)
14.18/4.51	   activate(X) -> X
14.18/4.51	
14.18/4.51	S is empty.
14.18/4.51	Rewrite Strategy: INNERMOST
14.42/4.57	EOF