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