464.05/291.53 WORST_CASE(Omega(n^1), O(n^2)) 464.05/291.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 464.05/291.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 464.05/291.54 464.05/291.54 464.05/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 464.05/291.54 464.05/291.54 (0) CpxTRS 464.05/291.54 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 464.05/291.54 (2) CdtProblem 464.05/291.54 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (4) CdtProblem 464.05/291.54 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (6) CdtProblem 464.05/291.54 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 87 ms] 464.05/291.54 (8) CdtProblem 464.05/291.54 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 15 ms] 464.05/291.54 (10) CdtProblem 464.05/291.54 (11) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (12) CdtProblem 464.05/291.54 (13) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (14) CdtProblem 464.05/291.54 (15) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (16) CdtProblem 464.05/291.54 (17) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (18) CdtProblem 464.05/291.54 (19) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (20) CdtProblem 464.05/291.54 (21) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (22) CdtProblem 464.05/291.54 (23) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (24) CdtProblem 464.05/291.54 (25) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (26) CdtProblem 464.05/291.54 (27) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (28) CdtProblem 464.05/291.54 (29) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (30) CdtProblem 464.05/291.54 (31) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (32) CdtProblem 464.05/291.54 (33) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 1884 ms] 464.05/291.54 (34) CdtProblem 464.05/291.54 (35) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (36) BOUNDS(1, 1) 464.05/291.54 (37) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (38) CpxTRS 464.05/291.54 (39) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 464.05/291.54 (40) typed CpxTrs 464.05/291.54 (41) OrderProof [LOWER BOUND(ID), 0 ms] 464.05/291.54 (42) typed CpxTrs 464.05/291.54 (43) RewriteLemmaProof [LOWER BOUND(ID), 190 ms] 464.05/291.54 (44) BEST 464.05/291.54 (45) proven lower bound 464.05/291.54 (46) LowerBoundPropagationProof [FINISHED, 0 ms] 464.05/291.54 (47) BOUNDS(n^1, INF) 464.05/291.54 (48) typed CpxTrs 464.05/291.54 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (0) 464.05/291.54 Obligation: 464.05/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 464.05/291.54 464.05/291.54 464.05/291.54 The TRS R consists of the following rules: 464.05/291.54 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(x)) -> f(x) 464.05/291.54 if(true, x, y) -> x 464.05/291.54 if(false, x, y) -> y 464.05/291.54 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.54 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.54 464.05/291.54 S is empty. 464.05/291.54 Rewrite Strategy: INNERMOST 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 464.05/291.54 Converted Cpx (relative) TRS to CDT 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (2) 464.05/291.54 Obligation: 464.05/291.54 Complexity Dependency Tuples Problem 464.05/291.54 464.05/291.54 Rules: 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(z0)) -> f(z0) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 Tuples: 464.05/291.54 F(0) -> c1 464.05/291.54 F(1) -> c2 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 IF(true, z0, z1) -> c4 464.05/291.54 IF(false, z0, z1) -> c5 464.05/291.54 G(s(z0), s(z1)) -> c6(IF(f(z0), s(z0), s(z1)), F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 S tuples: 464.05/291.54 F(0) -> c1 464.05/291.54 F(1) -> c2 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 IF(true, z0, z1) -> c4 464.05/291.54 IF(false, z0, z1) -> c5 464.05/291.54 G(s(z0), s(z1)) -> c6(IF(f(z0), s(z0), s(z1)), F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 K tuples:none 464.05/291.54 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.54 464.05/291.54 Defined Pair Symbols: F_1, IF_3, G_2 464.05/291.54 464.05/291.54 Compound Symbols: c1, c2, c3_1, c4, c5, c6_2, c7_2 464.05/291.54 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 464.05/291.54 Removed 4 trailing nodes: 464.05/291.54 IF(true, z0, z1) -> c4 464.05/291.54 F(0) -> c1 464.05/291.54 IF(false, z0, z1) -> c5 464.05/291.54 F(1) -> c2 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (4) 464.05/291.54 Obligation: 464.05/291.54 Complexity Dependency Tuples Problem 464.05/291.54 464.05/291.54 Rules: 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(z0)) -> f(z0) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 Tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(s(z0), s(z1)) -> c6(IF(f(z0), s(z0), s(z1)), F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 S tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(s(z0), s(z1)) -> c6(IF(f(z0), s(z0), s(z1)), F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 K tuples:none 464.05/291.54 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.54 464.05/291.54 Defined Pair Symbols: F_1, G_2 464.05/291.54 464.05/291.54 Compound Symbols: c3_1, c6_2, c7_2 464.05/291.54 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 464.05/291.54 Removed 1 trailing tuple parts 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (6) 464.05/291.54 Obligation: 464.05/291.54 Complexity Dependency Tuples Problem 464.05/291.54 464.05/291.54 Rules: 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(z0)) -> f(z0) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 Tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 S tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 K tuples:none 464.05/291.54 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.54 464.05/291.54 Defined Pair Symbols: F_1, G_2 464.05/291.54 464.05/291.54 Compound Symbols: c3_1, c7_2, c6_1 464.05/291.54 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 464.05/291.54 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 We considered the (Usable) Rules: 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 And the Tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 The order we found is given by the following interpretation: 464.05/291.54 464.05/291.54 Polynomial interpretation : 464.05/291.54 464.05/291.54 POL(0) = [1] 464.05/291.54 POL(1) = [1] 464.05/291.54 POL(F(x_1)) = 0 464.05/291.54 POL(G(x_1, x_2)) = [1] + x_1 + x_2 464.05/291.54 POL(c(x_1)) = [1] + x_1 464.05/291.54 POL(c3(x_1)) = x_1 464.05/291.54 POL(c6(x_1)) = x_1 464.05/291.54 POL(c7(x_1, x_2)) = x_1 + x_2 464.05/291.54 POL(f(x_1)) = [1] 464.05/291.54 POL(false) = [1] 464.05/291.54 POL(g(x_1, x_2)) = 0 464.05/291.54 POL(if(x_1, x_2, x_3)) = x_2 + x_3 464.05/291.54 POL(s(x_1)) = 0 464.05/291.54 POL(true) = [1] 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (8) 464.05/291.54 Obligation: 464.05/291.54 Complexity Dependency Tuples Problem 464.05/291.54 464.05/291.54 Rules: 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(z0)) -> f(z0) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 Tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 S tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 K tuples: 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.54 464.05/291.54 Defined Pair Symbols: F_1, G_2 464.05/291.54 464.05/291.54 Compound Symbols: c3_1, c7_2, c6_1 464.05/291.54 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 464.05/291.54 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 We considered the (Usable) Rules: 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 And the Tuples: 464.05/291.54 F(s(z0)) -> c3(F(z0)) 464.05/291.54 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.54 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.54 The order we found is given by the following interpretation: 464.05/291.54 464.05/291.54 Polynomial interpretation : 464.05/291.54 464.05/291.54 POL(0) = [1] 464.05/291.54 POL(1) = [1] 464.05/291.54 POL(F(x_1)) = 0 464.05/291.54 POL(G(x_1, x_2)) = x_1 + x_2 464.05/291.54 POL(c(x_1)) = [1] + x_1 464.05/291.54 POL(c3(x_1)) = x_1 464.05/291.54 POL(c6(x_1)) = x_1 464.05/291.54 POL(c7(x_1, x_2)) = x_1 + x_2 464.05/291.54 POL(f(x_1)) = [1] 464.05/291.54 POL(false) = [1] 464.05/291.54 POL(g(x_1, x_2)) = 0 464.05/291.54 POL(if(x_1, x_2, x_3)) = x_2 + x_3 464.05/291.54 POL(s(x_1)) = 0 464.05/291.54 POL(true) = [1] 464.05/291.54 464.05/291.54 ---------------------------------------- 464.05/291.54 464.05/291.54 (10) 464.05/291.54 Obligation: 464.05/291.54 Complexity Dependency Tuples Problem 464.05/291.54 464.05/291.54 Rules: 464.05/291.54 f(0) -> true 464.05/291.54 f(1) -> false 464.05/291.54 f(s(z0)) -> f(z0) 464.05/291.54 if(true, z0, z1) -> z0 464.05/291.54 if(false, z0, z1) -> z1 464.05/291.54 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 S tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: F_1, G_2 464.05/291.55 464.05/291.55 Compound Symbols: c3_1, c7_2, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (11) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use narrowing to replace G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) by 464.05/291.55 G(x0, c(s(z1))) -> c7(G(x0, if(f(c(s(z1))), s(c(s(z1))), s(z1))), G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(z1))) -> c7(G(x0, g(s(c(c(z1))), g(s(c(z1)), z1))), G(s(c(c(z1))), c(z1))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (12) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(x0, if(f(c(s(z1))), s(c(s(z1))), s(z1))), G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(z1))) -> c7(G(x0, g(s(c(c(z1))), g(s(c(z1)), z1))), G(s(c(c(z1))), c(z1))) 464.05/291.55 S tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: F_1, G_2 464.05/291.55 464.05/291.55 Compound Symbols: c3_1, c6_1, c7_2 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (13) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Removed 1 trailing tuple parts 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (14) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(x0, c(c(z1))) -> c7(G(x0, g(s(c(c(z1))), g(s(c(z1)), z1))), G(s(c(c(z1))), c(z1))) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 S tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: F_1, G_2 464.05/291.55 464.05/291.55 Compound Symbols: c3_1, c6_1, c7_2, c7_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (15) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use narrowing to replace G(x0, c(c(z1))) -> c7(G(x0, g(s(c(c(z1))), g(s(c(z1)), z1))), G(s(c(c(z1))), c(z1))) by 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(x0, g(s(c(c(s(z1)))), if(f(c(s(z1))), s(c(s(z1))), s(z1)))), G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (16) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(x0, g(s(c(c(s(z1)))), if(f(c(s(z1))), s(c(s(z1))), s(z1)))), G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 S tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: F_1, G_2 464.05/291.55 464.05/291.55 Compound Symbols: c3_1, c6_1, c7_1, c7_2 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (17) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Removed 1 trailing tuple parts 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (18) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 S tuples: 464.05/291.55 F(s(z0)) -> c3(F(z0)) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: F_1, G_2 464.05/291.55 464.05/291.55 Compound Symbols: c3_1, c6_1, c7_1, c7_2 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (19) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace F(s(z0)) -> c3(F(z0)) by 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (20) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 K tuples: 464.05/291.55 G(s(z0), s(z1)) -> c6(F(z0)) 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c6_1, c7_1, c7_2, c3_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (21) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace G(s(z0), s(z1)) -> c6(F(z0)) by 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (22) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 K tuples: 464.05/291.55 G(z0, c(z1)) -> c7(G(z0, g(s(c(z1)), z1)), G(s(c(z1)), z1)) 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_1, c7_2, c3_1, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (23) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Removed 2 trailing nodes: 464.05/291.55 G(x0, c(c(s(z1)))) -> c7(G(s(c(c(s(z1)))), c(s(z1)))) 464.05/291.55 G(x0, c(s(z1))) -> c7(G(s(c(s(z1))), s(z1))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (24) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c7_1, c3_1, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (25) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace G(x0, c(c(x1))) -> c7(G(s(c(c(x1))), c(x1))) by 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 G(z0, c(c(c(y1)))) -> c7(G(s(c(c(c(y1)))), c(c(y1)))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (26) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 G(z0, c(c(c(y1)))) -> c7(G(s(c(c(c(y1)))), c(c(y1)))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(y0))) -> c3(F(s(y0))) 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c3_1, c6_1, c7_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (27) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace F(s(s(y0))) -> c3(F(s(y0))) by 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (28) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 G(z0, c(c(c(y1)))) -> c7(G(s(c(c(c(y1)))), c(c(y1)))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c6_1, c7_1, c3_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (29) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace G(s(s(s(y0))), s(z1)) -> c6(F(s(s(y0)))) by 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (30) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 G(z0, c(c(c(y1)))) -> c7(G(s(c(c(c(y1)))), c(c(y1)))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c7_1, c3_1, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (31) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Use forward instantiation to replace G(z0, c(c(c(y1)))) -> c7(G(s(c(c(c(y1)))), c(c(y1)))) by 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 G(z0, c(c(c(c(c(y1)))))) -> c7(G(s(c(c(c(c(c(y1)))))), c(c(c(c(y1)))))) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (32) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 G(z0, c(c(c(c(c(y1)))))) -> c7(G(s(c(c(c(c(c(y1)))))), c(c(c(c(y1)))))) 464.05/291.55 S tuples: 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c7_1, c3_1, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (33) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 464.05/291.55 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 We considered the (Usable) Rules:none 464.05/291.55 And the Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 G(z0, c(c(c(c(c(y1)))))) -> c7(G(s(c(c(c(c(c(y1)))))), c(c(c(c(y1)))))) 464.05/291.55 The order we found is given by the following interpretation: 464.05/291.55 464.05/291.55 Matrix interpretation [MATRO]: 464.05/291.55 464.05/291.55 Non-tuple symbols: 464.05/291.55 <<< 464.05/291.55 M( s_1(x_1) ) = [[0], [2]] + [[1, 4], [0, 1]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( true ) = [[0], [0]] 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( c_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( f_1(x_1) ) = [[4], [0]] + [[0, 0], [0, 4]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( if_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( 0 ) = [[0], [2]] 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( 1 ) = [[0], [4]] 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( g_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( false ) = [[1], [4]] 464.05/291.55 >>> 464.05/291.55 464.05/291.55 Tuple symbols: 464.05/291.55 <<< 464.05/291.55 M( G_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( c6_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( c3_1(x_1) ) = [[0], [2]] + [[1, 2], [0, 1]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( F_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( c7_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 464.05/291.55 >>> 464.05/291.55 464.05/291.55 <<< 464.05/291.55 M( c7_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 464.05/291.55 >>> 464.05/291.55 464.05/291.55 464.05/291.55 464.05/291.55 Matrix type: 464.05/291.55 464.05/291.55 We used a basic matrix type which is not further parametrizeable. 464.05/291.55 464.05/291.55 464.05/291.55 464.05/291.55 464.05/291.55 464.05/291.55 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (34) 464.05/291.55 Obligation: 464.05/291.55 Complexity Dependency Tuples Problem 464.05/291.55 464.05/291.55 Rules: 464.05/291.55 f(0) -> true 464.05/291.55 f(1) -> false 464.05/291.55 f(s(z0)) -> f(z0) 464.05/291.55 if(true, z0, z1) -> z0 464.05/291.55 if(false, z0, z1) -> z1 464.05/291.55 g(s(z0), s(z1)) -> if(f(z0), s(z0), s(z1)) 464.05/291.55 g(z0, c(z1)) -> g(z0, g(s(c(z1)), z1)) 464.05/291.55 Tuples: 464.05/291.55 G(x0, c(c(c(z1)))) -> c7(G(x0, g(s(c(c(c(z1)))), g(s(c(c(z1))), g(s(c(z1)), z1)))), G(s(c(c(c(z1)))), c(c(z1)))) 464.05/291.55 G(z0, c(c(c(c(y1))))) -> c7(G(s(c(c(c(c(y1))))), c(c(c(y1))))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 G(z0, c(c(c(c(c(y1)))))) -> c7(G(s(c(c(c(c(c(y1)))))), c(c(c(c(y1)))))) 464.05/291.55 S tuples:none 464.05/291.55 K tuples: 464.05/291.55 G(s(s(s(s(y0)))), s(z1)) -> c6(F(s(s(s(y0))))) 464.05/291.55 F(s(s(s(y0)))) -> c3(F(s(s(y0)))) 464.05/291.55 Defined Rule Symbols: f_1, if_3, g_2 464.05/291.55 464.05/291.55 Defined Pair Symbols: G_2, F_1 464.05/291.55 464.05/291.55 Compound Symbols: c7_2, c7_1, c3_1, c6_1 464.05/291.55 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (35) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 The set S is empty 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (36) 464.05/291.55 BOUNDS(1, 1) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (37) RenamingProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Renamed function symbols to avoid clashes with predefined symbol. 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (38) 464.05/291.55 Obligation: 464.05/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 464.05/291.55 464.05/291.55 464.05/291.55 The TRS R consists of the following rules: 464.05/291.55 464.05/291.55 f(0') -> true 464.05/291.55 f(1') -> false 464.05/291.55 f(s(x)) -> f(x) 464.05/291.55 if(true, x, y) -> x 464.05/291.55 if(false, x, y) -> y 464.05/291.55 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.55 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.55 464.05/291.55 S is empty. 464.05/291.55 Rewrite Strategy: INNERMOST 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (39) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 464.05/291.55 Infered types. 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (40) 464.05/291.55 Obligation: 464.05/291.55 Innermost TRS: 464.05/291.55 Rules: 464.05/291.55 f(0') -> true 464.05/291.55 f(1') -> false 464.05/291.55 f(s(x)) -> f(x) 464.05/291.55 if(true, x, y) -> x 464.05/291.55 if(false, x, y) -> y 464.05/291.55 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.55 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.55 464.05/291.55 Types: 464.05/291.55 f :: 0':1':s:c -> true:false 464.05/291.55 0' :: 0':1':s:c 464.05/291.55 true :: true:false 464.05/291.55 1' :: 0':1':s:c 464.05/291.55 false :: true:false 464.05/291.55 s :: 0':1':s:c -> 0':1':s:c 464.05/291.55 if :: true:false -> 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 g :: 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 c :: 0':1':s:c -> 0':1':s:c 464.05/291.55 hole_true:false1_0 :: true:false 464.05/291.55 hole_0':1':s:c2_0 :: 0':1':s:c 464.05/291.55 gen_0':1':s:c3_0 :: Nat -> 0':1':s:c 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (41) OrderProof (LOWER BOUND(ID)) 464.05/291.55 Heuristically decided to analyse the following defined symbols: 464.05/291.55 f, g 464.05/291.55 464.05/291.55 They will be analysed ascendingly in the following order: 464.05/291.55 f < g 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (42) 464.05/291.55 Obligation: 464.05/291.55 Innermost TRS: 464.05/291.55 Rules: 464.05/291.55 f(0') -> true 464.05/291.55 f(1') -> false 464.05/291.55 f(s(x)) -> f(x) 464.05/291.55 if(true, x, y) -> x 464.05/291.55 if(false, x, y) -> y 464.05/291.55 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.55 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.55 464.05/291.55 Types: 464.05/291.55 f :: 0':1':s:c -> true:false 464.05/291.55 0' :: 0':1':s:c 464.05/291.55 true :: true:false 464.05/291.55 1' :: 0':1':s:c 464.05/291.55 false :: true:false 464.05/291.55 s :: 0':1':s:c -> 0':1':s:c 464.05/291.55 if :: true:false -> 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 g :: 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 c :: 0':1':s:c -> 0':1':s:c 464.05/291.55 hole_true:false1_0 :: true:false 464.05/291.55 hole_0':1':s:c2_0 :: 0':1':s:c 464.05/291.55 gen_0':1':s:c3_0 :: Nat -> 0':1':s:c 464.05/291.55 464.05/291.55 464.05/291.55 Generator Equations: 464.05/291.55 gen_0':1':s:c3_0(0) <=> 0' 464.05/291.55 gen_0':1':s:c3_0(+(x, 1)) <=> s(gen_0':1':s:c3_0(x)) 464.05/291.55 464.05/291.55 464.05/291.55 The following defined symbols remain to be analysed: 464.05/291.55 f, g 464.05/291.55 464.05/291.55 They will be analysed ascendingly in the following order: 464.05/291.55 f < g 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (43) RewriteLemmaProof (LOWER BOUND(ID)) 464.05/291.55 Proved the following rewrite lemma: 464.05/291.55 f(gen_0':1':s:c3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 464.05/291.55 464.05/291.55 Induction Base: 464.05/291.55 f(gen_0':1':s:c3_0(0)) ->_R^Omega(1) 464.05/291.55 true 464.05/291.55 464.05/291.55 Induction Step: 464.05/291.55 f(gen_0':1':s:c3_0(+(n5_0, 1))) ->_R^Omega(1) 464.05/291.55 f(gen_0':1':s:c3_0(n5_0)) ->_IH 464.05/291.55 true 464.05/291.55 464.05/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (44) 464.05/291.55 Complex Obligation (BEST) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (45) 464.05/291.55 Obligation: 464.05/291.55 Proved the lower bound n^1 for the following obligation: 464.05/291.55 464.05/291.55 Innermost TRS: 464.05/291.55 Rules: 464.05/291.55 f(0') -> true 464.05/291.55 f(1') -> false 464.05/291.55 f(s(x)) -> f(x) 464.05/291.55 if(true, x, y) -> x 464.05/291.55 if(false, x, y) -> y 464.05/291.55 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.55 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.55 464.05/291.55 Types: 464.05/291.55 f :: 0':1':s:c -> true:false 464.05/291.55 0' :: 0':1':s:c 464.05/291.55 true :: true:false 464.05/291.55 1' :: 0':1':s:c 464.05/291.55 false :: true:false 464.05/291.55 s :: 0':1':s:c -> 0':1':s:c 464.05/291.55 if :: true:false -> 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 g :: 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 c :: 0':1':s:c -> 0':1':s:c 464.05/291.55 hole_true:false1_0 :: true:false 464.05/291.55 hole_0':1':s:c2_0 :: 0':1':s:c 464.05/291.55 gen_0':1':s:c3_0 :: Nat -> 0':1':s:c 464.05/291.55 464.05/291.55 464.05/291.55 Generator Equations: 464.05/291.55 gen_0':1':s:c3_0(0) <=> 0' 464.05/291.55 gen_0':1':s:c3_0(+(x, 1)) <=> s(gen_0':1':s:c3_0(x)) 464.05/291.55 464.05/291.55 464.05/291.55 The following defined symbols remain to be analysed: 464.05/291.55 f, g 464.05/291.55 464.05/291.55 They will be analysed ascendingly in the following order: 464.05/291.55 f < g 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (46) LowerBoundPropagationProof (FINISHED) 464.05/291.55 Propagated lower bound. 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (47) 464.05/291.55 BOUNDS(n^1, INF) 464.05/291.55 464.05/291.55 ---------------------------------------- 464.05/291.55 464.05/291.55 (48) 464.05/291.55 Obligation: 464.05/291.55 Innermost TRS: 464.05/291.55 Rules: 464.05/291.55 f(0') -> true 464.05/291.55 f(1') -> false 464.05/291.55 f(s(x)) -> f(x) 464.05/291.55 if(true, x, y) -> x 464.05/291.55 if(false, x, y) -> y 464.05/291.55 g(s(x), s(y)) -> if(f(x), s(x), s(y)) 464.05/291.55 g(x, c(y)) -> g(x, g(s(c(y)), y)) 464.05/291.55 464.05/291.55 Types: 464.05/291.55 f :: 0':1':s:c -> true:false 464.05/291.55 0' :: 0':1':s:c 464.05/291.55 true :: true:false 464.05/291.55 1' :: 0':1':s:c 464.05/291.55 false :: true:false 464.05/291.55 s :: 0':1':s:c -> 0':1':s:c 464.05/291.55 if :: true:false -> 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 g :: 0':1':s:c -> 0':1':s:c -> 0':1':s:c 464.05/291.55 c :: 0':1':s:c -> 0':1':s:c 464.05/291.55 hole_true:false1_0 :: true:false 464.05/291.55 hole_0':1':s:c2_0 :: 0':1':s:c 464.05/291.55 gen_0':1':s:c3_0 :: Nat -> 0':1':s:c 464.05/291.55 464.05/291.55 464.05/291.55 Lemmas: 464.05/291.55 f(gen_0':1':s:c3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 464.05/291.55 464.05/291.55 464.05/291.55 Generator Equations: 464.05/291.55 gen_0':1':s:c3_0(0) <=> 0' 464.05/291.55 gen_0':1':s:c3_0(+(x, 1)) <=> s(gen_0':1':s:c3_0(x)) 464.05/291.55 464.05/291.55 464.05/291.55 The following defined symbols remain to be analysed: 464.05/291.55 g 464.17/291.59 EOF