WORST_CASE(Omega(n^1), O(n^2)) 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^2). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (4) CdtProblem (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 57 ms] (8) CdtProblem (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 9 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 16 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^2). The TRS R consists of the following rules: selects(x', revprefix, Cons(x, xs)) -> Cons(Cons(x', revapp(revprefix, Cons(x, xs))), selects(x, Cons(x', revprefix), xs)) select(Cons(x, xs)) -> selects(x, Nil, xs) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) selects(x, revprefix, Nil) -> Cons(Cons(x, revapp(revprefix, Nil)), Nil) select(Nil) -> Nil revapp(Nil, rest) -> rest S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: selects(z0, z1, Cons(z2, z3)) -> Cons(Cons(z0, revapp(z1, Cons(z2, z3))), selects(z2, Cons(z0, z1), z3)) selects(z0, z1, Nil) -> Cons(Cons(z0, revapp(z1, Nil)), Nil) select(Cons(z0, z1)) -> selects(z0, Nil, z1) select(Nil) -> Nil revapp(Cons(z0, z1), z2) -> revapp(z1, Cons(z0, z2)) revapp(Nil, z0) -> z0 Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) SELECT(Cons(z0, z1)) -> c2(SELECTS(z0, Nil, z1)) SELECT(Nil) -> c3 REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) REVAPP(Nil, z0) -> c5 S tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) SELECT(Cons(z0, z1)) -> c2(SELECTS(z0, Nil, z1)) SELECT(Nil) -> c3 REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) REVAPP(Nil, z0) -> c5 K tuples:none Defined Rule Symbols: selects_3, select_1, revapp_2 Defined Pair Symbols: SELECTS_3, SELECT_1, REVAPP_2 Compound Symbols: c_2, c1_1, c2_1, c3, c4_1, c5 ---------------------------------------- (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 1 leading nodes: SELECT(Cons(z0, z1)) -> c2(SELECTS(z0, Nil, z1)) Removed 2 trailing nodes: SELECT(Nil) -> c3 REVAPP(Nil, z0) -> c5 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: selects(z0, z1, Cons(z2, z3)) -> Cons(Cons(z0, revapp(z1, Cons(z2, z3))), selects(z2, Cons(z0, z1), z3)) selects(z0, z1, Nil) -> Cons(Cons(z0, revapp(z1, Nil)), Nil) select(Cons(z0, z1)) -> selects(z0, Nil, z1) select(Nil) -> Nil revapp(Cons(z0, z1), z2) -> revapp(z1, Cons(z0, z2)) revapp(Nil, z0) -> z0 Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) S tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) K tuples:none Defined Rule Symbols: selects_3, select_1, revapp_2 Defined Pair Symbols: SELECTS_3, REVAPP_2 Compound Symbols: c_2, c1_1, c4_1 ---------------------------------------- (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: selects(z0, z1, Cons(z2, z3)) -> Cons(Cons(z0, revapp(z1, Cons(z2, z3))), selects(z2, Cons(z0, z1), z3)) selects(z0, z1, Nil) -> Cons(Cons(z0, revapp(z1, Nil)), Nil) select(Cons(z0, z1)) -> selects(z0, Nil, z1) select(Nil) -> Nil revapp(Cons(z0, z1), z2) -> revapp(z1, Cons(z0, z2)) revapp(Nil, z0) -> z0 ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) S tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: SELECTS_3, REVAPP_2 Compound Symbols: c_2, c1_1, c4_1 ---------------------------------------- (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) We considered the (Usable) Rules:none And the Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(Cons(x_1, x_2)) = [1] + x_1 + x_2 POL(Nil) = [1] POL(REVAPP(x_1, x_2)) = [1] POL(SELECTS(x_1, x_2, x_3)) = [1] + x_1 + x_3 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c4(x_1)) = x_1 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) S tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) K tuples: SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) Defined Rule Symbols:none Defined Pair Symbols: SELECTS_3, REVAPP_2 Compound Symbols: c_2, c1_1, c4_1 ---------------------------------------- (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) We considered the (Usable) Rules:none And the Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(Cons(x_1, x_2)) = [1] + x_1 + x_2 POL(Nil) = [1] POL(REVAPP(x_1, x_2)) = 0 POL(SELECTS(x_1, x_2, x_3)) = [1] + x_1 + x_3 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c4(x_1)) = x_1 ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) S tuples: REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) K tuples: SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) Defined Rule Symbols:none Defined Pair Symbols: SELECTS_3, REVAPP_2 Compound Symbols: c_2, c1_1, c4_1 ---------------------------------------- (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) We considered the (Usable) Rules:none And the Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(Cons(x_1, x_2)) = [2] + x_2 POL(Nil) = [2] POL(REVAPP(x_1, x_2)) = [2]x_1 POL(SELECTS(x_1, x_2, x_3)) = [2] + [2]x_3 + [2]x_3^2 + [2]x_2*x_3 POL(c(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(c4(x_1)) = x_1 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) S tuples:none K tuples: SELECTS(z0, z1, Nil) -> c1(REVAPP(z1, Nil)) SELECTS(z0, z1, Cons(z2, z3)) -> c(REVAPP(z1, Cons(z2, z3)), SELECTS(z2, Cons(z0, z1), z3)) REVAPP(Cons(z0, z1), z2) -> c4(REVAPP(z1, Cons(z0, z2))) Defined Rule Symbols:none Defined Pair Symbols: SELECTS_3, REVAPP_2 Compound Symbols: c_2, c1_1, c4_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^2). The TRS R consists of the following rules: selects(x', revprefix, Cons(x, xs)) -> Cons(Cons(x', revapp(revprefix, Cons(x, xs))), selects(x, Cons(x', revprefix), xs)) select(Cons(x, xs)) -> selects(x, Nil, xs) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) selects(x, revprefix, Nil) -> Cons(Cons(x, revapp(revprefix, Nil)), Nil) select(Nil) -> Nil revapp(Nil, rest) -> rest 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 selects(x', revprefix, Cons(x, xs)) ->^+ Cons(Cons(x', revapp(revprefix, Cons(x, xs))), selects(x, Cons(x', revprefix), xs)) gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. The pumping substitution is [xs / Cons(x, xs)]. The result substitution is [x' / x, revprefix / Cons(x', revprefix)]. ---------------------------------------- (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^2). The TRS R consists of the following rules: selects(x', revprefix, Cons(x, xs)) -> Cons(Cons(x', revapp(revprefix, Cons(x, xs))), selects(x, Cons(x', revprefix), xs)) select(Cons(x, xs)) -> selects(x, Nil, xs) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) selects(x, revprefix, Nil) -> Cons(Cons(x, revapp(revprefix, Nil)), Nil) select(Nil) -> Nil revapp(Nil, rest) -> rest 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^2). The TRS R consists of the following rules: selects(x', revprefix, Cons(x, xs)) -> Cons(Cons(x', revapp(revprefix, Cons(x, xs))), selects(x, Cons(x', revprefix), xs)) select(Cons(x, xs)) -> selects(x, Nil, xs) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) selects(x, revprefix, Nil) -> Cons(Cons(x, revapp(revprefix, Nil)), Nil) select(Nil) -> Nil revapp(Nil, rest) -> rest S is empty. Rewrite Strategy: INNERMOST