/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/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)), 74 ms] (12) CdtProblem (13) CdtKnowledgeProof [FINISHED, 0 ms] (14) BOUNDS(1, 1) (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (16) TRS for Loop Detection (17) DecreasingLoopProof [LOWER BOUND(ID), 166 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: U11(tt, N, X, XS) -> U12(splitAt(activate(N), activate(XS)), activate(X)) U12(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) afterNth(N, XS) -> snd(splitAt(N, XS)) and(tt, X) -> activate(X) fst(pair(X, Y)) -> X head(cons(N, XS)) -> N natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> head(afterNth(N, XS)) snd(pair(X, Y)) -> Y splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U11(tt, N, X, activate(XS)) tail(cons(N, XS)) -> activate(XS) take(N, XS) -> fst(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: U11(tt, z0, z1, z2) -> U12(splitAt(activate(z0), activate(z2)), activate(z1)) U12(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) afterNth(z0, z1) -> snd(splitAt(z0, z1)) and(tt, z0) -> activate(z0) fst(pair(z0, z1)) -> z0 head(cons(z0, z1)) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> head(afterNth(z0, z1)) snd(pair(z0, z1)) -> z1 splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U11(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> activate(z1) take(z0, z1) -> fst(splitAt(z0, z1)) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: 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)) U12'(pair(z0, z1), z2) -> c1(ACTIVATE(z2)) AFTERNTH(z0, z1) -> c2(SND(splitAt(z0, z1)), SPLITAT(z0, z1)) AND(tt, z0) -> c3(ACTIVATE(z0)) FST(pair(z0, z1)) -> c4 HEAD(cons(z0, z1)) -> c5 NATSFROM(z0) -> c6 NATSFROM(z0) -> c7 SEL(z0, z1) -> c8(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1)) SND(pair(z0, z1)) -> c9 SPLITAT(0, z0) -> c10 SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAIL(cons(z0, z1)) -> c12(ACTIVATE(z1)) TAKE(z0, z1) -> c13(FST(splitAt(z0, z1)), SPLITAT(z0, z1)) ACTIVATE(n__natsFrom(z0)) -> c14(NATSFROM(z0)) ACTIVATE(z0) -> c15 S tuples: 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)) U12'(pair(z0, z1), z2) -> c1(ACTIVATE(z2)) AFTERNTH(z0, z1) -> c2(SND(splitAt(z0, z1)), SPLITAT(z0, z1)) AND(tt, z0) -> c3(ACTIVATE(z0)) FST(pair(z0, z1)) -> c4 HEAD(cons(z0, z1)) -> c5 NATSFROM(z0) -> c6 NATSFROM(z0) -> c7 SEL(z0, z1) -> c8(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1)) SND(pair(z0, z1)) -> c9 SPLITAT(0, z0) -> c10 SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAIL(cons(z0, z1)) -> c12(ACTIVATE(z1)) TAKE(z0, z1) -> c13(FST(splitAt(z0, z1)), SPLITAT(z0, z1)) ACTIVATE(n__natsFrom(z0)) -> c14(NATSFROM(z0)) ACTIVATE(z0) -> c15 K tuples:none 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 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 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 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 11 trailing nodes: SND(pair(z0, z1)) -> c9 ACTIVATE(n__natsFrom(z0)) -> c14(NATSFROM(z0)) HEAD(cons(z0, z1)) -> c5 ACTIVATE(z0) -> c15 NATSFROM(z0) -> c6 TAIL(cons(z0, z1)) -> c12(ACTIVATE(z1)) NATSFROM(z0) -> c7 SPLITAT(0, z0) -> c10 FST(pair(z0, z1)) -> c4 AND(tt, z0) -> c3(ACTIVATE(z0)) U12'(pair(z0, z1), z2) -> c1(ACTIVATE(z2)) ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1, z2) -> U12(splitAt(activate(z0), activate(z2)), activate(z1)) U12(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) afterNth(z0, z1) -> snd(splitAt(z0, z1)) and(tt, z0) -> activate(z0) fst(pair(z0, z1)) -> z0 head(cons(z0, z1)) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> head(afterNth(z0, z1)) snd(pair(z0, z1)) -> z1 splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U11(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> activate(z1) take(z0, z1) -> fst(splitAt(z0, z1)) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: 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)) AFTERNTH(z0, z1) -> c2(SND(splitAt(z0, z1)), SPLITAT(z0, z1)) SEL(z0, z1) -> c8(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAKE(z0, z1) -> c13(FST(splitAt(z0, z1)), SPLITAT(z0, z1)) S tuples: 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)) AFTERNTH(z0, z1) -> c2(SND(splitAt(z0, z1)), SPLITAT(z0, z1)) SEL(z0, z1) -> c8(HEAD(afterNth(z0, z1)), AFTERNTH(z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAKE(z0, z1) -> c13(FST(splitAt(z0, z1)), SPLITAT(z0, z1)) K tuples:none 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 Defined Pair Symbols: U11'_4, AFTERNTH_2, SEL_2, SPLITAT_2, TAKE_2 Compound Symbols: c_5, c2_2, c8_2, c11_2, c13_2 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 8 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1, z2) -> U12(splitAt(activate(z0), activate(z2)), activate(z1)) U12(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) afterNth(z0, z1) -> snd(splitAt(z0, z1)) and(tt, z0) -> activate(z0) fst(pair(z0, z1)) -> z0 head(cons(z0, z1)) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> head(afterNth(z0, z1)) snd(pair(z0, z1)) -> z1 splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U11(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> activate(z1) take(z0, z1) -> fst(splitAt(z0, z1)) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) AFTERNTH(z0, z1) -> c2(SPLITAT(z0, z1)) SEL(z0, z1) -> c8(AFTERNTH(z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) TAKE(z0, z1) -> c13(SPLITAT(z0, z1)) S tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) AFTERNTH(z0, z1) -> c2(SPLITAT(z0, z1)) SEL(z0, z1) -> c8(AFTERNTH(z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) TAKE(z0, z1) -> c13(SPLITAT(z0, z1)) K tuples:none 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 Defined Pair Symbols: U11'_4, AFTERNTH_2, SEL_2, SPLITAT_2, TAKE_2 Compound Symbols: c_1, c2_1, c8_1, c11_1, c13_1 ---------------------------------------- (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 3 leading nodes: SEL(z0, z1) -> c8(AFTERNTH(z0, z1)) AFTERNTH(z0, z1) -> c2(SPLITAT(z0, z1)) TAKE(z0, z1) -> c13(SPLITAT(z0, z1)) ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1, z2) -> U12(splitAt(activate(z0), activate(z2)), activate(z1)) U12(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) afterNth(z0, z1) -> snd(splitAt(z0, z1)) and(tt, z0) -> activate(z0) fst(pair(z0, z1)) -> z0 head(cons(z0, z1)) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> head(afterNth(z0, z1)) snd(pair(z0, z1)) -> z1 splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U11(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> activate(z1) take(z0, z1) -> fst(splitAt(z0, z1)) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) S tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) K tuples:none 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 Defined Pair Symbols: U11'_4, SPLITAT_2 Compound Symbols: c_1, c11_1 ---------------------------------------- (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: U11(tt, z0, z1, z2) -> U12(splitAt(activate(z0), activate(z2)), activate(z1)) U12(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) afterNth(z0, z1) -> snd(splitAt(z0, z1)) and(tt, z0) -> activate(z0) fst(pair(z0, z1)) -> z0 head(cons(z0, z1)) -> z0 sel(z0, z1) -> head(afterNth(z0, z1)) snd(pair(z0, z1)) -> z1 splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U11(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> activate(z1) take(z0, z1) -> fst(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: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) S tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) K tuples:none Defined Rule Symbols: activate_1, natsFrom_1 Defined Pair Symbols: U11'_4, SPLITAT_2 Compound Symbols: c_1, c11_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)) -> c11(U11'(tt, z0, z1, 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: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(SPLITAT(x_1, x_2)) = [1] + x_1 + x_2 POL(U11'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_4 POL(activate(x_1)) = x_1 POL(c(x_1)) = x_1 POL(c11(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 POL(tt) = [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: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) S tuples: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) K tuples: SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) Defined Rule Symbols: activate_1, natsFrom_1 Defined Pair Symbols: U11'_4, SPLITAT_2 Compound Symbols: c_1, c11_1 ---------------------------------------- (13) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: U11'(tt, z0, z1, z2) -> c(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c11(U11'(tt, z0, z1, activate(z2))) Now 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: U11(tt, N, X, XS) -> U12(splitAt(activate(N), activate(XS)), activate(X)) U12(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) afterNth(N, XS) -> snd(splitAt(N, XS)) and(tt, X) -> activate(X) fst(pair(X, Y)) -> X head(cons(N, XS)) -> N natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> head(afterNth(N, XS)) snd(pair(X, Y)) -> Y splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U11(tt, N, X, activate(XS)) tail(cons(N, XS)) -> activate(XS) take(N, XS) -> fst(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 U11(tt, s(N1_0), X, cons(X2_0, XS3_0)) ->^+ U12(U11(tt, N1_0, X2_0, XS3_0), activate(X)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [N1_0 / s(N1_0), XS3_0 / cons(X2_0, XS3_0)]. The result substitution is [X / X2_0]. ---------------------------------------- (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: U11(tt, N, X, XS) -> U12(splitAt(activate(N), activate(XS)), activate(X)) U12(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) afterNth(N, XS) -> snd(splitAt(N, XS)) and(tt, X) -> activate(X) fst(pair(X, Y)) -> X head(cons(N, XS)) -> N natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> head(afterNth(N, XS)) snd(pair(X, Y)) -> Y splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U11(tt, N, X, activate(XS)) tail(cons(N, XS)) -> activate(XS) take(N, XS) -> fst(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: U11(tt, N, X, XS) -> U12(splitAt(activate(N), activate(XS)), activate(X)) U12(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) afterNth(N, XS) -> snd(splitAt(N, XS)) and(tt, X) -> activate(X) fst(pair(X, Y)) -> X head(cons(N, XS)) -> N natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> head(afterNth(N, XS)) snd(pair(X, Y)) -> Y splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U11(tt, N, X, activate(XS)) tail(cons(N, XS)) -> activate(XS) take(N, XS) -> fst(splitAt(N, XS)) natsFrom(X) -> n__natsFrom(X) activate(n__natsFrom(X)) -> natsFrom(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST