21.36/7.02 WORST_CASE(Omega(n^1), O(n^1)) 21.36/7.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 21.36/7.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.36/7.03 21.36/7.03 21.36/7.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.36/7.03 21.36/7.03 (0) CpxTRS 21.36/7.03 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (2) CpxTRS 21.36/7.03 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 21.36/7.03 (4) CdtProblem 21.36/7.03 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (6) CdtProblem 21.36/7.03 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (8) CdtProblem 21.36/7.03 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 85 ms] 21.36/7.03 (10) CdtProblem 21.36/7.03 (11) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 2 ms] 21.36/7.03 (12) CdtProblem 21.36/7.03 (13) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (14) CdtProblem 21.36/7.03 (15) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (16) CdtProblem 21.36/7.03 (17) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 21.36/7.03 (18) CdtProblem 21.36/7.03 (19) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (20) CdtProblem 21.36/7.03 (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms] 21.36/7.03 (22) CdtProblem 21.36/7.03 (23) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 21.36/7.03 (24) BOUNDS(1, 1) 21.36/7.03 (25) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 21.36/7.03 (26) TRS for Loop Detection 21.36/7.03 (27) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 21.36/7.03 (28) BEST 21.36/7.03 (29) proven lower bound 21.36/7.03 (30) LowerBoundPropagationProof [FINISHED, 0 ms] 21.36/7.03 (31) BOUNDS(n^1, INF) 21.36/7.03 (32) TRS for Loop Detection 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (0) 21.36/7.03 Obligation: 21.36/7.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.36/7.03 21.36/7.03 21.36/7.03 The TRS R consists of the following rules: 21.36/7.03 21.36/7.03 f(x, 0) -> s(0) 21.36/7.03 f(s(x), s(y)) -> s(f(x, y)) 21.36/7.03 g(0, x) -> g(f(x, x), x) 21.36/7.03 21.36/7.03 S is empty. 21.36/7.03 Rewrite Strategy: FULL 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 Converted rc-obligation to irc-obligation. 21.36/7.03 21.36/7.03 The duplicating contexts are: 21.36/7.03 g(0, []) 21.36/7.03 21.36/7.03 21.36/7.03 The defined contexts are: 21.36/7.03 g([], x1) 21.36/7.03 21.36/7.03 21.36/7.03 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (2) 21.36/7.03 Obligation: 21.36/7.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 21.36/7.03 21.36/7.03 21.36/7.03 The TRS R consists of the following rules: 21.36/7.03 21.36/7.03 f(x, 0) -> s(0) 21.36/7.03 f(s(x), s(y)) -> s(f(x, y)) 21.36/7.03 g(0, x) -> g(f(x, x), x) 21.36/7.03 21.36/7.03 S is empty. 21.36/7.03 Rewrite Strategy: INNERMOST 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 21.36/7.03 Converted Cpx (relative) TRS to CDT 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (4) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 g(0, z0) -> g(f(z0, z0), z0) 21.36/7.03 Tuples: 21.36/7.03 F(z0, 0) -> c 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 S tuples: 21.36/7.03 F(z0, 0) -> c 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2, g_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c, c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 Removed 1 trailing nodes: 21.36/7.03 F(z0, 0) -> c 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (6) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 g(0, z0) -> g(f(z0, z0), z0) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2, g_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 The following rules are not usable and were removed: 21.36/7.03 g(0, z0) -> g(f(z0, z0), z0) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (8) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 21.36/7.03 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 We considered the (Usable) Rules: 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 And the Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 The order we found is given by the following interpretation: 21.36/7.03 21.36/7.03 Polynomial interpretation : 21.36/7.03 21.36/7.03 POL(0) = [1] 21.36/7.03 POL(F(x_1, x_2)) = 0 21.36/7.03 POL(G(x_1, x_2)) = x_1 21.36/7.03 POL(c1(x_1)) = x_1 21.36/7.03 POL(c2(x_1, x_2)) = x_1 + x_2 21.36/7.03 POL(f(x_1, x_2)) = 0 21.36/7.03 POL(s(x_1)) = 0 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (10) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples: 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (11) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 Use narrowing to replace G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) by 21.36/7.03 G(0, 0) -> c2(G(s(0), 0), F(0, 0)) 21.36/7.03 G(0, s(z0)) -> c2(G(s(f(z0, z0)), s(z0)), F(s(z0), s(z0))) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (12) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, 0) -> c2(G(s(0), 0), F(0, 0)) 21.36/7.03 G(0, s(z0)) -> c2(G(s(f(z0, z0)), s(z0)), F(s(z0), s(z0))) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples: 21.36/7.03 G(0, z0) -> c2(G(f(z0, z0), z0), F(z0, z0)) 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (13) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 Removed 1 trailing nodes: 21.36/7.03 G(0, 0) -> c2(G(s(0), 0), F(0, 0)) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (14) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, s(z0)) -> c2(G(s(f(z0, z0)), s(z0)), F(s(z0), s(z0))) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_2 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (15) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 Removed 1 trailing tuple parts 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (16) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 G(0, s(z0)) -> c2(F(s(z0), s(z0))) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2, G_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1, c2_1 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (17) CdtLeafRemovalProof (ComplexityIfPolyImplication) 21.36/7.03 Removed 1 leading nodes: 21.36/7.03 G(0, s(z0)) -> c2(F(s(z0), s(z0))) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (18) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols: f_2 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (19) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 The following rules are not usable and were removed: 21.36/7.03 f(z0, 0) -> s(0) 21.36/7.03 f(s(z0), s(z1)) -> s(f(z0, z1)) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (20) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules:none 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 S tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 K tuples:none 21.36/7.03 Defined Rule Symbols:none 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 21.36/7.03 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 We considered the (Usable) Rules:none 21.36/7.03 And the Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 The order we found is given by the following interpretation: 21.36/7.03 21.36/7.03 Polynomial interpretation : 21.36/7.03 21.36/7.03 POL(F(x_1, x_2)) = x_2 21.36/7.03 POL(c1(x_1)) = x_1 21.36/7.03 POL(s(x_1)) = [1] + x_1 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (22) 21.36/7.03 Obligation: 21.36/7.03 Complexity Dependency Tuples Problem 21.36/7.03 21.36/7.03 Rules:none 21.36/7.03 Tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 S tuples:none 21.36/7.03 K tuples: 21.36/7.03 F(s(z0), s(z1)) -> c1(F(z0, z1)) 21.36/7.03 Defined Rule Symbols:none 21.36/7.03 21.36/7.03 Defined Pair Symbols: F_2 21.36/7.03 21.36/7.03 Compound Symbols: c1_1 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (23) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 21.36/7.03 The set S is empty 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (24) 21.36/7.03 BOUNDS(1, 1) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (25) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 21.36/7.03 Transformed a relative TRS into a decreasing-loop problem. 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (26) 21.36/7.03 Obligation: 21.36/7.03 Analyzing the following TRS for decreasing loops: 21.36/7.03 21.36/7.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.36/7.03 21.36/7.03 21.36/7.03 The TRS R consists of the following rules: 21.36/7.03 21.36/7.03 f(x, 0) -> s(0) 21.36/7.03 f(s(x), s(y)) -> s(f(x, y)) 21.36/7.03 g(0, x) -> g(f(x, x), x) 21.36/7.03 21.36/7.03 S is empty. 21.36/7.03 Rewrite Strategy: FULL 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (27) DecreasingLoopProof (LOWER BOUND(ID)) 21.36/7.03 The following loop(s) give(s) rise to the lower bound Omega(n^1): 21.36/7.03 21.36/7.03 The rewrite sequence 21.36/7.03 21.36/7.03 f(s(x), s(y)) ->^+ s(f(x, y)) 21.36/7.03 21.36/7.03 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 21.36/7.03 21.36/7.03 The pumping substitution is [x / s(x), y / s(y)]. 21.36/7.03 21.36/7.03 The result substitution is [ ]. 21.36/7.03 21.36/7.03 21.36/7.03 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (28) 21.36/7.03 Complex Obligation (BEST) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (29) 21.36/7.03 Obligation: 21.36/7.03 Proved the lower bound n^1 for the following obligation: 21.36/7.03 21.36/7.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.36/7.03 21.36/7.03 21.36/7.03 The TRS R consists of the following rules: 21.36/7.03 21.36/7.03 f(x, 0) -> s(0) 21.36/7.03 f(s(x), s(y)) -> s(f(x, y)) 21.36/7.03 g(0, x) -> g(f(x, x), x) 21.36/7.03 21.36/7.03 S is empty. 21.36/7.03 Rewrite Strategy: FULL 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (30) LowerBoundPropagationProof (FINISHED) 21.36/7.03 Propagated lower bound. 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (31) 21.36/7.03 BOUNDS(n^1, INF) 21.36/7.03 21.36/7.03 ---------------------------------------- 21.36/7.03 21.36/7.03 (32) 21.36/7.03 Obligation: 21.36/7.03 Analyzing the following TRS for decreasing loops: 21.36/7.03 21.36/7.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.36/7.03 21.36/7.03 21.36/7.03 The TRS R consists of the following rules: 21.36/7.03 21.36/7.03 f(x, 0) -> s(0) 21.36/7.03 f(s(x), s(y)) -> s(f(x, y)) 21.36/7.03 g(0, x) -> g(f(x, x), x) 21.36/7.03 21.36/7.03 S is empty. 21.36/7.03 Rewrite Strategy: FULL 21.56/10.57 EOF