/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), 1 ms] (4) CdtProblem (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 31 ms] (10) CdtProblem (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 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^1). The TRS R consists of the following rules: admit(x, nil) -> nil admit(x, .(u, .(v, .(w, z)))) -> cond(=(sum(x, u, v), w), .(u, .(v, .(w, admit(carry(x, u, v), z))))) cond(true, y) -> 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: admit(z0, nil) -> nil admit(z0, .(z1, .(z2, .(w, z3)))) -> cond(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))) cond(true, z0) -> z0 Tuples: ADMIT(z0, nil) -> c ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(COND(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))), ADMIT(carry(z0, z1, z2), z3)) COND(true, z0) -> c2 S tuples: ADMIT(z0, nil) -> c ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(COND(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))), ADMIT(carry(z0, z1, z2), z3)) COND(true, z0) -> c2 K tuples:none Defined Rule Symbols: admit_2, cond_2 Defined Pair Symbols: ADMIT_2, COND_2 Compound Symbols: c, c1_2, c2 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing nodes: COND(true, z0) -> c2 ADMIT(z0, nil) -> c ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: admit(z0, nil) -> nil admit(z0, .(z1, .(z2, .(w, z3)))) -> cond(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))) cond(true, z0) -> z0 Tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(COND(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))), ADMIT(carry(z0, z1, z2), z3)) S tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(COND(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))), ADMIT(carry(z0, z1, z2), z3)) K tuples:none Defined Rule Symbols: admit_2, cond_2 Defined Pair Symbols: ADMIT_2 Compound Symbols: c1_2 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: admit(z0, nil) -> nil admit(z0, .(z1, .(z2, .(w, z3)))) -> cond(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))) cond(true, z0) -> z0 Tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) S tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) K tuples:none Defined Rule Symbols: admit_2, cond_2 Defined Pair Symbols: ADMIT_2 Compound Symbols: c1_1 ---------------------------------------- (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: admit(z0, nil) -> nil admit(z0, .(z1, .(z2, .(w, z3)))) -> cond(=(sum(z0, z1, z2), w), .(z1, .(z2, .(w, admit(carry(z0, z1, z2), z3))))) cond(true, z0) -> z0 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) S tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: ADMIT_2 Compound Symbols: c1_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. ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) We considered the (Usable) Rules:none And the Tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(.(x_1, x_2)) = [1] + x_1 + x_2 POL(ADMIT(x_1, x_2)) = x_1 + x_2 POL(c1(x_1)) = x_1 POL(carry(x_1, x_2, x_3)) = x_2 + x_3 POL(w) = 0 ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) S tuples:none K tuples: ADMIT(z0, .(z1, .(z2, .(w, z3)))) -> c1(ADMIT(carry(z0, z1, z2), z3)) Defined Rule Symbols:none Defined Pair Symbols: ADMIT_2 Compound Symbols: c1_1 ---------------------------------------- (11) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set 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^1). The TRS R consists of the following rules: admit(x, nil) -> nil admit(x, .(u, .(v, .(w, z)))) -> cond(=(sum(x, u, v), w), .(u, .(v, .(w, admit(carry(x, u, v), z))))) cond(true, y) -> y 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 admit(x, .(u, .(v, .(w, z)))) ->^+ cond(=(sum(x, u, v), w), .(u, .(v, .(w, admit(carry(x, u, v), z))))) gives rise to a decreasing loop by considering the right hand sides subterm at position [1,1,1,1]. The pumping substitution is [z / .(u, .(v, .(w, z)))]. The result substitution is [x / carry(x, u, v)]. ---------------------------------------- (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^1). The TRS R consists of the following rules: admit(x, nil) -> nil admit(x, .(u, .(v, .(w, z)))) -> cond(=(sum(x, u, v), w), .(u, .(v, .(w, admit(carry(x, u, v), z))))) cond(true, y) -> y 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^1). The TRS R consists of the following rules: admit(x, nil) -> nil admit(x, .(u, .(v, .(w, z)))) -> cond(=(sum(x, u, v), w), .(u, .(v, .(w, admit(carry(x, u, v), z))))) cond(true, y) -> y S is empty. Rewrite Strategy: INNERMOST