/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), 11 ms] (2) CdtProblem (3) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 79 ms] (4) CdtProblem (5) CdtInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 12 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: f(x, c(y)) -> f(x, s(f(y, y))) f(s(x), s(y)) -> f(x, s(c(s(y)))) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: f(z0, c(z1)) -> f(z0, s(f(z1, z1))) f(s(z0), s(z1)) -> f(z0, s(c(s(z1)))) Tuples: F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) S tuples: F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) K tuples:none Defined Rule Symbols: f_2 Defined Pair Symbols: F_2 Compound Symbols: c1_2, c2_1 ---------------------------------------- (3) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) We considered the (Usable) Rules:none And the Tuples: F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) The order we found is given by the following interpretation: Polynomial interpretation : POL(F(x_1, x_2)) = x_2 POL(c(x_1)) = [1] + x_1 POL(c1(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(f(x_1, x_2)) = [1] + x_2 POL(s(x_1)) = 0 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: f(z0, c(z1)) -> f(z0, s(f(z1, z1))) f(s(z0), s(z1)) -> f(z0, s(c(s(z1)))) Tuples: F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) S tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) K tuples: F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) Defined Rule Symbols: f_2 Defined Pair Symbols: F_2 Compound Symbols: c1_2, c2_1 ---------------------------------------- (5) CdtInstantiationProof (BOTH BOUNDS(ID, ID)) Use instantiation to replace F(z0, c(z1)) -> c1(F(z0, s(f(z1, z1))), F(z1, z1)) by F(c(z1), c(z1)) -> c1(F(c(z1), s(f(z1, z1))), F(z1, z1)) ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: f(z0, c(z1)) -> f(z0, s(f(z1, z1))) f(s(z0), s(z1)) -> f(z0, s(c(s(z1)))) Tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) F(c(z1), c(z1)) -> c1(F(c(z1), s(f(z1, z1))), F(z1, z1)) S tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) K tuples: F(c(z1), c(z1)) -> c1(F(c(z1), s(f(z1, z1))), F(z1, z1)) Defined Rule Symbols: f_2 Defined Pair Symbols: F_2 Compound Symbols: c2_1, c1_2 ---------------------------------------- (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: f(z0, c(z1)) -> f(z0, s(f(z1, z1))) f(s(z0), s(z1)) -> f(z0, s(c(s(z1)))) Tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) F(c(z1), c(z1)) -> c1(F(z1, z1)) S tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) K tuples: F(c(z1), c(z1)) -> c1(F(z1, z1)) Defined Rule Symbols: f_2 Defined Pair Symbols: F_2 Compound Symbols: c2_1, c1_1 ---------------------------------------- (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: f(z0, c(z1)) -> f(z0, s(f(z1, z1))) f(s(z0), s(z1)) -> f(z0, s(c(s(z1)))) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) F(c(z1), c(z1)) -> c1(F(z1, z1)) S tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) K tuples: F(c(z1), c(z1)) -> c1(F(z1, z1)) Defined Rule Symbols:none Defined Pair Symbols: F_2 Compound Symbols: c2_1, c1_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. F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) We considered the (Usable) Rules:none And the Tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) F(c(z1), c(z1)) -> c1(F(z1, z1)) The order we found is given by the following interpretation: Polynomial interpretation : POL(F(x_1, x_2)) = [2]x_1^2 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(s(x_1)) = [2] + x_1 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) F(c(z1), c(z1)) -> c1(F(z1, z1)) S tuples:none K tuples: F(c(z1), c(z1)) -> c1(F(z1, z1)) F(s(z0), s(z1)) -> c2(F(z0, s(c(s(z1))))) Defined Rule Symbols:none Defined Pair Symbols: F_2 Compound Symbols: c2_1, c1_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: f(x, c(y)) -> f(x, s(f(y, y))) f(s(x), s(y)) -> f(x, s(c(s(y)))) 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 f(x, c(y)) ->^+ f(x, s(f(y, y))) gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0]. The pumping substitution is [y / c(y)]. The result substitution is [x / y]. ---------------------------------------- (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: f(x, c(y)) -> f(x, s(f(y, y))) f(s(x), s(y)) -> f(x, s(c(s(y)))) 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: f(x, c(y)) -> f(x, s(f(y, y))) f(s(x), s(y)) -> f(x, s(c(s(y)))) S is empty. Rewrite Strategy: INNERMOST