WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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), 0 ms] (8) CdtProblem (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 21 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (3) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: a__f(z0, z0) -> a__f(a, b) a__f(z0, z1) -> f(z0, z1) a__b -> a a__b -> b mark(f(z0, z1)) -> a__f(mark(z0), z1) mark(b) -> a__b mark(a) -> a Tuples: A__F(z0, z0) -> c(A__F(a, b)) A__F(z0, z1) -> c1 A__B -> c2 A__B -> c3 MARK(f(z0, z1)) -> c4(A__F(mark(z0), z1), MARK(z0)) MARK(b) -> c5(A__B) MARK(a) -> c6 S tuples: A__F(z0, z0) -> c(A__F(a, b)) A__F(z0, z1) -> c1 A__B -> c2 A__B -> c3 MARK(f(z0, z1)) -> c4(A__F(mark(z0), z1), MARK(z0)) MARK(b) -> c5(A__B) MARK(a) -> c6 K tuples:none Defined Rule Symbols: a__f_2, a__b, mark_1 Defined Pair Symbols: A__F_2, A__B, MARK_1 Compound Symbols: c_1, c1, c2, c3, c4_2, c5_1, c6 ---------------------------------------- (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 6 trailing nodes: A__B -> c3 A__F(z0, z1) -> c1 A__F(z0, z0) -> c(A__F(a, b)) A__B -> c2 MARK(b) -> c5(A__B) MARK(a) -> c6 ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: a__f(z0, z0) -> a__f(a, b) a__f(z0, z1) -> f(z0, z1) a__b -> a a__b -> b mark(f(z0, z1)) -> a__f(mark(z0), z1) mark(b) -> a__b mark(a) -> a Tuples: MARK(f(z0, z1)) -> c4(A__F(mark(z0), z1), MARK(z0)) S tuples: MARK(f(z0, z1)) -> c4(A__F(mark(z0), z1), MARK(z0)) K tuples:none Defined Rule Symbols: a__f_2, a__b, mark_1 Defined Pair Symbols: MARK_1 Compound Symbols: c4_2 ---------------------------------------- (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: a__f(z0, z0) -> a__f(a, b) a__f(z0, z1) -> f(z0, z1) a__b -> a a__b -> b mark(f(z0, z1)) -> a__f(mark(z0), z1) mark(b) -> a__b mark(a) -> a Tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) S tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) K tuples:none Defined Rule Symbols: a__f_2, a__b, mark_1 Defined Pair Symbols: MARK_1 Compound Symbols: c4_1 ---------------------------------------- (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: a__f(z0, z0) -> a__f(a, b) a__f(z0, z1) -> f(z0, z1) a__b -> a a__b -> b mark(f(z0, z1)) -> a__f(mark(z0), z1) mark(b) -> a__b mark(a) -> a ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) S tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: MARK_1 Compound Symbols: c4_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. MARK(f(z0, z1)) -> c4(MARK(z0)) We considered the (Usable) Rules:none And the Tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) The order we found is given by the following interpretation: Polynomial interpretation : POL(MARK(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(f(x_1, x_2)) = [1] + x_1 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) S tuples:none K tuples: MARK(f(z0, z1)) -> c4(MARK(z0)) Defined Rule Symbols:none Defined Pair Symbols: MARK_1 Compound Symbols: 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 (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b 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 mark(f(X1, X2)) ->^+ a__f(mark(X1), X2) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [X1 / f(X1, X2)]. The result substitution is [ ]. ---------------------------------------- (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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b S is empty. Rewrite Strategy: FULL