329.61/291.48 WORST_CASE(Omega(n^1), O(n^2)) 329.61/291.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 329.61/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 329.61/291.49 329.61/291.49 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 329.61/291.49 329.61/291.49 (0) CpxTRS 329.61/291.49 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 329.61/291.49 (2) CpxTRS 329.61/291.49 (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 4 ms] 329.61/291.49 (4) CpxTRS 329.61/291.49 (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 329.61/291.49 (6) CdtProblem 329.61/291.49 (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 329.61/291.49 (8) CdtProblem 329.61/291.49 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 329.61/291.49 (10) CdtProblem 329.61/291.49 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 15 ms] 329.61/291.49 (12) CdtProblem 329.61/291.49 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 329.61/291.49 (14) BOUNDS(1, 1) 329.61/291.49 (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 329.61/291.49 (16) TRS for Loop Detection 329.61/291.49 (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 329.61/291.49 (18) BEST 329.61/291.49 (19) proven lower bound 329.61/291.49 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 329.61/291.49 (21) BOUNDS(n^1, INF) 329.61/291.49 (22) TRS for Loop Detection 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (0) 329.61/291.49 Obligation: 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 d(z, g(0, 0)) -> e(0) 329.61/291.49 d(z, g(x, y)) -> g(e(x), d(z, y)) 329.61/291.49 d(c(z), g(g(x, y), 0)) -> g(d(c(z), g(x, y)), d(z, g(x, y))) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: FULL 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 329.61/291.49 The following defined symbols can occur below the 1th argument of h: d 329.61/291.49 The following defined symbols can occur below the 1th argument of d: d 329.61/291.49 329.61/291.49 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 329.61/291.49 d(z, g(0, 0)) -> e(0) 329.61/291.49 d(z, g(x, y)) -> g(e(x), d(z, y)) 329.61/291.49 d(c(z), g(g(x, y), 0)) -> g(d(c(z), g(x, y)), d(z, g(x, y))) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (2) 329.61/291.49 Obligation: 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: FULL 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) 329.61/291.49 Converted rc-obligation to irc-obligation. 329.61/291.49 329.61/291.49 As the TRS does not nest defined symbols, we have rc = irc. 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (4) 329.61/291.49 Obligation: 329.61/291.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: INNERMOST 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (5) CpxTrsToCdtProof (UPPER BOUND(ID)) 329.61/291.49 Converted Cpx (relative) TRS to CDT 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (6) 329.61/291.49 Obligation: 329.61/291.49 Complexity Dependency Tuples Problem 329.61/291.49 329.61/291.49 Rules: 329.61/291.49 h(z0, e(z1)) -> h(c(z0), d(z0, z1)) 329.61/291.49 g(e(z0), e(z1)) -> e(g(z0, z1)) 329.61/291.49 Tuples: 329.61/291.49 H(z0, e(z1)) -> c1(H(c(z0), d(z0, z1))) 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 S tuples: 329.61/291.49 H(z0, e(z1)) -> c1(H(c(z0), d(z0, z1))) 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 K tuples:none 329.61/291.49 Defined Rule Symbols: h_2, g_2 329.61/291.49 329.61/291.49 Defined Pair Symbols: H_2, G_2 329.61/291.49 329.61/291.49 Compound Symbols: c1_1, c2_1 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 329.61/291.49 Removed 1 trailing nodes: 329.61/291.49 H(z0, e(z1)) -> c1(H(c(z0), d(z0, z1))) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (8) 329.61/291.49 Obligation: 329.61/291.49 Complexity Dependency Tuples Problem 329.61/291.49 329.61/291.49 Rules: 329.61/291.49 h(z0, e(z1)) -> h(c(z0), d(z0, z1)) 329.61/291.49 g(e(z0), e(z1)) -> e(g(z0, z1)) 329.61/291.49 Tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 S tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 K tuples:none 329.61/291.49 Defined Rule Symbols: h_2, g_2 329.61/291.49 329.61/291.49 Defined Pair Symbols: G_2 329.61/291.49 329.61/291.49 Compound Symbols: c2_1 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 329.61/291.49 The following rules are not usable and were removed: 329.61/291.49 h(z0, e(z1)) -> h(c(z0), d(z0, z1)) 329.61/291.49 g(e(z0), e(z1)) -> e(g(z0, z1)) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (10) 329.61/291.49 Obligation: 329.61/291.49 Complexity Dependency Tuples Problem 329.61/291.49 329.61/291.49 Rules:none 329.61/291.49 Tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 S tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 K tuples:none 329.61/291.49 Defined Rule Symbols:none 329.61/291.49 329.61/291.49 Defined Pair Symbols: G_2 329.61/291.49 329.61/291.49 Compound Symbols: c2_1 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 329.61/291.49 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 We considered the (Usable) Rules:none 329.61/291.49 And the Tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 The order we found is given by the following interpretation: 329.61/291.49 329.61/291.49 Polynomial interpretation : 329.61/291.49 329.61/291.49 POL(G(x_1, x_2)) = [2]x_2^2 329.61/291.49 POL(c2(x_1)) = x_1 329.61/291.49 POL(e(x_1)) = [1] + x_1 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (12) 329.61/291.49 Obligation: 329.61/291.49 Complexity Dependency Tuples Problem 329.61/291.49 329.61/291.49 Rules:none 329.61/291.49 Tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 S tuples:none 329.61/291.49 K tuples: 329.61/291.49 G(e(z0), e(z1)) -> c2(G(z0, z1)) 329.61/291.49 Defined Rule Symbols:none 329.61/291.49 329.61/291.49 Defined Pair Symbols: G_2 329.61/291.49 329.61/291.49 Compound Symbols: c2_1 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 329.61/291.49 The set S is empty 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (14) 329.61/291.49 BOUNDS(1, 1) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 329.61/291.49 Transformed a relative TRS into a decreasing-loop problem. 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (16) 329.61/291.49 Obligation: 329.61/291.49 Analyzing the following TRS for decreasing loops: 329.61/291.49 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 d(z, g(0, 0)) -> e(0) 329.61/291.49 d(z, g(x, y)) -> g(e(x), d(z, y)) 329.61/291.49 d(c(z), g(g(x, y), 0)) -> g(d(c(z), g(x, y)), d(z, g(x, y))) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: FULL 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (17) DecreasingLoopProof (LOWER BOUND(ID)) 329.61/291.49 The following loop(s) give(s) rise to the lower bound Omega(n^1): 329.61/291.49 329.61/291.49 The rewrite sequence 329.61/291.49 329.61/291.49 g(e(x), e(y)) ->^+ e(g(x, y)) 329.61/291.49 329.61/291.49 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 329.61/291.49 329.61/291.49 The pumping substitution is [x / e(x), y / e(y)]. 329.61/291.49 329.61/291.49 The result substitution is [ ]. 329.61/291.49 329.61/291.49 329.61/291.49 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (18) 329.61/291.49 Complex Obligation (BEST) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (19) 329.61/291.49 Obligation: 329.61/291.49 Proved the lower bound n^1 for the following obligation: 329.61/291.49 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 d(z, g(0, 0)) -> e(0) 329.61/291.49 d(z, g(x, y)) -> g(e(x), d(z, y)) 329.61/291.49 d(c(z), g(g(x, y), 0)) -> g(d(c(z), g(x, y)), d(z, g(x, y))) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: FULL 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (20) LowerBoundPropagationProof (FINISHED) 329.61/291.49 Propagated lower bound. 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (21) 329.61/291.49 BOUNDS(n^1, INF) 329.61/291.49 329.61/291.49 ---------------------------------------- 329.61/291.49 329.61/291.49 (22) 329.61/291.49 Obligation: 329.61/291.49 Analyzing the following TRS for decreasing loops: 329.61/291.49 329.61/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 329.61/291.49 329.61/291.49 329.61/291.49 The TRS R consists of the following rules: 329.61/291.49 329.61/291.49 h(z, e(x)) -> h(c(z), d(z, x)) 329.61/291.49 d(z, g(0, 0)) -> e(0) 329.61/291.49 d(z, g(x, y)) -> g(e(x), d(z, y)) 329.61/291.49 d(c(z), g(g(x, y), 0)) -> g(d(c(z), g(x, y)), d(z, g(x, y))) 329.61/291.49 g(e(x), e(y)) -> e(g(x, y)) 329.61/291.49 329.61/291.49 S is empty. 329.61/291.49 Rewrite Strategy: FULL 329.61/291.52 EOF