/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^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (4) CdtProblem (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 1 ms] (8) CdtProblem (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 30 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 (full) 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: FULL ---------------------------------------- (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. The duplicating contexts are: admit([], .(u, .(v, .(w, z)))) admit(x, .([], .(v, .(w, z)))) admit(x, .(u, .([], .(w, z)))) The defined contexts are: cond(=(sum(x0, x1, x2), w), .(x3, .(x4, .(w, [])))) As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(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 ---------------------------------------- (3) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (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, 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 ---------------------------------------- (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing nodes: ADMIT(z0, nil) -> c COND(true, z0) -> c2 ---------------------------------------- (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(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 ---------------------------------------- (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (8) 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 ---------------------------------------- (9) 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 ---------------------------------------- (10) 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 ---------------------------------------- (11) 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 ---------------------------------------- (12) 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 ---------------------------------------- (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 (full) 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: FULL ---------------------------------------- (17) 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)]. ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (full) 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: FULL ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^1, INF) ---------------------------------------- (22) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) 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: FULL