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