/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^2)) 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^2). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CdtProblem (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 2 ms] (6) CdtProblem (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 64 ms] (8) CdtProblem (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 38 ms] (10) CdtProblem (11) CdtKnowledgeProof [FINISHED, 0 ms] (12) BOUNDS(1, 1) (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (14) TRS for Loop Detection (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (16) BEST (17) proven lower bound (18) LowerBoundPropagationProof [FINISHED, 0 ms] (19) BOUNDS(n^1, INF) (20) 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: from(X) -> cons(X, n__from(s(X))) first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) sel(0, cons(X, Z)) -> X sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) from(X) -> n__from(X) first(X1, X2) -> n__first(X1, X2) activate(n__from(X)) -> from(X) activate(n__first(X1, X2)) -> first(X1, X2) 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: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) first(0, z0) -> nil first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(z0, z1) -> n__first(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__first(z0, z1)) -> first(z0, z1) activate(z0) -> z0 Tuples: FROM(z0) -> c FROM(z0) -> c1 FIRST(0, z0) -> c2 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) FIRST(z0, z1) -> c4 SEL(0, cons(z0, z1)) -> c5 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__from(z0)) -> c7(FROM(z0)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) ACTIVATE(z0) -> c9 S tuples: FROM(z0) -> c FROM(z0) -> c1 FIRST(0, z0) -> c2 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) FIRST(z0, z1) -> c4 SEL(0, cons(z0, z1)) -> c5 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__from(z0)) -> c7(FROM(z0)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) ACTIVATE(z0) -> c9 K tuples:none Defined Rule Symbols: from_1, first_2, sel_2, activate_1 Defined Pair Symbols: FROM_1, FIRST_2, SEL_2, ACTIVATE_1 Compound Symbols: c, c1, c2, c3_1, c4, c5, c6_2, c7_1, c8_1, c9 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 7 trailing nodes: ACTIVATE(n__from(z0)) -> c7(FROM(z0)) FIRST(z0, z1) -> c4 FROM(z0) -> c1 ACTIVATE(z0) -> c9 FIRST(0, z0) -> c2 SEL(0, cons(z0, z1)) -> c5 FROM(z0) -> c ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) first(0, z0) -> nil first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(z0, z1) -> n__first(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__first(z0, z1)) -> first(z0, z1) activate(z0) -> z0 Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) S tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) K tuples:none Defined Rule Symbols: from_1, first_2, sel_2, activate_1 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 Compound Symbols: c3_1, c6_2, c8_1 ---------------------------------------- (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__first(z0, z1)) -> first(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) first(0, z0) -> nil first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(z0, z1) -> n__first(z0, z1) Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) S tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) K tuples:none Defined Rule Symbols: activate_1, from_1, first_2 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 Compound Symbols: c3_1, c6_2, c8_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. SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) We considered the (Usable) Rules:none And the Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = 0 POL(FIRST(x_1, x_2)) = 0 POL(SEL(x_1, x_2)) = x_1 POL(activate(x_1)) = [1] POL(c3(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(cons(x_1, x_2)) = [1] + x_1 POL(first(x_1, x_2)) = [1] + x_1 + x_2 POL(from(x_1)) = [1] + x_1 POL(n__first(x_1, x_2)) = [1] + x_1 + x_2 POL(n__from(x_1)) = [1] + x_1 POL(nil) = [1] POL(s(x_1)) = [1] + x_1 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__first(z0, z1)) -> first(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) first(0, z0) -> nil first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(z0, z1) -> n__first(z0, z1) Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) S tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) K tuples: SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) Defined Rule Symbols: activate_1, from_1, first_2 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 Compound Symbols: c3_1, c6_2, c8_1 ---------------------------------------- (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) We considered the (Usable) Rules: first(z0, z1) -> n__first(z0, z1) from(z0) -> cons(z0, n__from(s(z0))) first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(0, z0) -> nil from(z0) -> n__from(z0) activate(n__from(z0)) -> from(z0) activate(z0) -> z0 activate(n__first(z0, z1)) -> first(z0, z1) And the Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = x_1 POL(FIRST(x_1, x_2)) = x_2 POL(SEL(x_1, x_2)) = x_1*x_2 POL(activate(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(cons(x_1, x_2)) = x_2 POL(first(x_1, x_2)) = [1] + x_2 POL(from(x_1)) = [1] POL(n__first(x_1, x_2)) = [1] + x_2 POL(n__from(x_1)) = [1] POL(nil) = [1] POL(s(x_1)) = [1] + x_1 ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__first(z0, z1)) -> first(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) first(0, z0) -> nil first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) first(z0, z1) -> n__first(z0, z1) Tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) S tuples: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) K tuples: SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) Defined Rule Symbols: activate_1, from_1, first_2 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 Compound Symbols: c3_1, c6_2, c8_1 ---------------------------------------- (11) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) Now S is empty ---------------------------------------- (12) BOUNDS(1, 1) ---------------------------------------- (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (14) 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: from(X) -> cons(X, n__from(s(X))) first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) sel(0, cons(X, Z)) -> X sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) from(X) -> n__from(X) first(X1, X2) -> n__first(X1, X2) activate(n__from(X)) -> from(X) activate(n__first(X1, X2)) -> first(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (15) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence sel(s(X), cons(Y, Z)) ->^+ sel(X, Z) gives rise to a decreasing loop by considering the right hand sides subterm at position []. The pumping substitution is [X / s(X), Z / cons(Y, Z)]. The result substitution is [ ]. ---------------------------------------- (16) Complex Obligation (BEST) ---------------------------------------- (17) 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: from(X) -> cons(X, n__from(s(X))) first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) sel(0, cons(X, Z)) -> X sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) from(X) -> n__from(X) first(X1, X2) -> n__first(X1, X2) activate(n__from(X)) -> from(X) activate(n__first(X1, X2)) -> first(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (18) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (19) BOUNDS(n^1, INF) ---------------------------------------- (20) 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: from(X) -> cons(X, n__from(s(X))) first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) sel(0, cons(X, Z)) -> X sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) from(X) -> n__from(X) first(X1, X2) -> n__first(X1, X2) activate(n__from(X)) -> from(X) activate(n__first(X1, X2)) -> first(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST