322.15/291.59 WORST_CASE(Omega(n^1), O(n^2)) 322.24/291.60 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 322.24/291.60 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 322.24/291.60 322.24/291.60 322.24/291.60 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 322.24/291.60 322.24/291.60 (0) CpxTRS 322.24/291.60 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 322.24/291.60 (2) CdtProblem 322.24/291.60 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 322.24/291.60 (4) CdtProblem 322.24/291.60 (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 322.24/291.60 (6) CdtProblem 322.24/291.60 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 85 ms] 322.24/291.60 (8) CdtProblem 322.24/291.60 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 84 ms] 322.24/291.60 (10) CdtProblem 322.24/291.60 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 83 ms] 322.24/291.60 (12) CdtProblem 322.24/291.60 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 95 ms] 322.24/291.60 (14) CdtProblem 322.24/291.60 (15) CdtKnowledgeProof [FINISHED, 0 ms] 322.24/291.60 (16) BOUNDS(1, 1) 322.24/291.60 (17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 322.24/291.60 (18) TRS for Loop Detection 322.24/291.60 (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 322.24/291.60 (20) BEST 322.24/291.60 (21) proven lower bound 322.24/291.60 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 322.24/291.60 (23) BOUNDS(n^1, INF) 322.24/291.60 (24) TRS for Loop Detection 322.24/291.60 322.24/291.60 322.24/291.60 ---------------------------------------- 322.24/291.60 322.24/291.60 (0) 322.24/291.60 Obligation: 322.24/291.60 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 322.24/291.60 322.24/291.60 322.24/291.60 The TRS R consists of the following rules: 322.24/291.60 322.24/291.60 eq(0, 0) -> true 322.24/291.60 eq(0, s(X)) -> false 322.24/291.60 eq(s(X), 0) -> false 322.24/291.60 eq(s(X), s(Y)) -> eq(X, Y) 322.24/291.60 rm(N, nil) -> nil 322.24/291.60 rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X)) 322.24/291.60 ifrm(true, N, add(M, X)) -> rm(N, X) 322.24/291.60 ifrm(false, N, add(M, X)) -> add(M, rm(N, X)) 322.24/291.60 purge(nil) -> nil 322.24/291.60 purge(add(N, X)) -> add(N, purge(rm(N, X))) 322.24/291.60 322.24/291.60 S is empty. 322.24/291.60 Rewrite Strategy: INNERMOST 322.24/291.60 ---------------------------------------- 322.24/291.60 322.24/291.60 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 322.24/291.60 Converted Cpx (relative) TRS to CDT 322.24/291.60 ---------------------------------------- 322.24/291.60 322.24/291.60 (2) 322.24/291.60 Obligation: 322.24/291.60 Complexity Dependency Tuples Problem 322.24/291.60 322.24/291.60 Rules: 322.24/291.60 eq(0, 0) -> true 322.24/291.60 eq(0, s(z0)) -> false 322.24/291.60 eq(s(z0), 0) -> false 322.24/291.60 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1))) 322.24/291.61 Tuples: 322.24/291.61 EQ(0, 0) -> c 322.24/291.61 EQ(0, s(z0)) -> c1 322.24/291.61 EQ(s(z0), 0) -> c2 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, nil) -> c4 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(nil) -> c8 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 EQ(0, 0) -> c 322.24/291.61 EQ(0, s(z0)) -> c1 322.24/291.61 EQ(s(z0), 0) -> c2 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, nil) -> c4 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(nil) -> c8 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 K tuples:none 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3, purge_1 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c, c1, c2, c3_1, c4, c5_2, c6_1, c7_1, c8, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 322.24/291.61 Removed 5 trailing nodes: 322.24/291.61 EQ(s(z0), 0) -> c2 322.24/291.61 EQ(0, s(z0)) -> c1 322.24/291.61 PURGE(nil) -> c8 322.24/291.61 EQ(0, 0) -> c 322.24/291.61 RM(z0, nil) -> c4 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (4) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1))) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 K tuples:none 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3, purge_1 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 322.24/291.61 The following rules are not usable and were removed: 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1))) 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (6) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 K tuples:none 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 322.24/291.61 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 We considered the (Usable) Rules: 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 And the Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 The order we found is given by the following interpretation: 322.24/291.61 322.24/291.61 Polynomial interpretation : 322.24/291.61 322.24/291.61 POL(0) = [1] 322.24/291.61 POL(EQ(x_1, x_2)) = 0 322.24/291.61 POL(IFRM(x_1, x_2, x_3)) = 0 322.24/291.61 POL(PURGE(x_1)) = x_1 322.24/291.61 POL(RM(x_1, x_2)) = 0 322.24/291.61 POL(add(x_1, x_2)) = [1] + x_1 + x_2 322.24/291.61 POL(c3(x_1)) = x_1 322.24/291.61 POL(c5(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(c6(x_1)) = x_1 322.24/291.61 POL(c7(x_1)) = x_1 322.24/291.61 POL(c9(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(eq(x_1, x_2)) = [1] + x_1 + x_2 322.24/291.61 POL(false) = [1] 322.24/291.61 POL(ifrm(x_1, x_2, x_3)) = x_2 + x_3 322.24/291.61 POL(nil) = [1] 322.24/291.61 POL(rm(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(s(x_1)) = [1] + x_1 322.24/291.61 POL(true) = [1] 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (8) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 K tuples: 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 322.24/291.61 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 We considered the (Usable) Rules: 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 And the Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 The order we found is given by the following interpretation: 322.24/291.61 322.24/291.61 Polynomial interpretation : 322.24/291.61 322.24/291.61 POL(0) = 0 322.24/291.61 POL(EQ(x_1, x_2)) = x_1 322.24/291.61 POL(IFRM(x_1, x_2, x_3)) = [2]x_2*x_3 322.24/291.61 POL(PURGE(x_1)) = [2]x_1^2 322.24/291.61 POL(RM(x_1, x_2)) = [2]x_1 + [2]x_1*x_2 322.24/291.61 POL(add(x_1, x_2)) = [2] + x_1 + x_2 322.24/291.61 POL(c3(x_1)) = x_1 322.24/291.61 POL(c5(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(c6(x_1)) = x_1 322.24/291.61 POL(c7(x_1)) = x_1 322.24/291.61 POL(c9(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(eq(x_1, x_2)) = 0 322.24/291.61 POL(false) = 0 322.24/291.61 POL(ifrm(x_1, x_2, x_3)) = x_3 322.24/291.61 POL(nil) = 0 322.24/291.61 POL(rm(x_1, x_2)) = x_2 322.24/291.61 POL(s(x_1)) = [2] + x_1 322.24/291.61 POL(true) = 0 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (10) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 K tuples: 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 322.24/291.61 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 We considered the (Usable) Rules: 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 eq(0, 0) -> true 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 And the Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 The order we found is given by the following interpretation: 322.24/291.61 322.24/291.61 Polynomial interpretation : 322.24/291.61 322.24/291.61 POL(0) = [1] 322.24/291.61 POL(EQ(x_1, x_2)) = 0 322.24/291.61 POL(IFRM(x_1, x_2, x_3)) = x_1 + [2]x_2*x_3 322.24/291.61 POL(PURGE(x_1)) = x_1^2 322.24/291.61 POL(RM(x_1, x_2)) = [2]x_1 + [2]x_1*x_2 322.24/291.61 POL(add(x_1, x_2)) = [1] + x_1 + x_2 322.24/291.61 POL(c3(x_1)) = x_1 322.24/291.61 POL(c5(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(c6(x_1)) = x_1 322.24/291.61 POL(c7(x_1)) = x_1 322.24/291.61 POL(c9(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(eq(x_1, x_2)) = x_1 322.24/291.61 POL(false) = [1] 322.24/291.61 POL(ifrm(x_1, x_2, x_3)) = x_3 322.24/291.61 POL(nil) = 0 322.24/291.61 POL(rm(x_1, x_2)) = x_2 322.24/291.61 POL(s(x_1)) = [1] + x_1 322.24/291.61 POL(true) = 0 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (12) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 K tuples: 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 322.24/291.61 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 We considered the (Usable) Rules: 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 And the Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 The order we found is given by the following interpretation: 322.24/291.61 322.24/291.61 Polynomial interpretation : 322.24/291.61 322.24/291.61 POL(0) = 0 322.24/291.61 POL(EQ(x_1, x_2)) = 0 322.24/291.61 POL(IFRM(x_1, x_2, x_3)) = [2]x_3 322.24/291.61 POL(PURGE(x_1)) = [2]x_1^2 322.24/291.61 POL(RM(x_1, x_2)) = [2]x_2 322.24/291.61 POL(add(x_1, x_2)) = [1] + x_2 322.24/291.61 POL(c3(x_1)) = x_1 322.24/291.61 POL(c5(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(c6(x_1)) = x_1 322.24/291.61 POL(c7(x_1)) = x_1 322.24/291.61 POL(c9(x_1, x_2)) = x_1 + x_2 322.24/291.61 POL(eq(x_1, x_2)) = 0 322.24/291.61 POL(false) = 0 322.24/291.61 POL(ifrm(x_1, x_2, x_3)) = x_3 322.24/291.61 POL(nil) = 0 322.24/291.61 POL(rm(x_1, x_2)) = x_2 322.24/291.61 POL(s(x_1)) = 0 322.24/291.61 POL(true) = 0 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (14) 322.24/291.61 Obligation: 322.24/291.61 Complexity Dependency Tuples Problem 322.24/291.61 322.24/291.61 Rules: 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(z0)) -> false 322.24/291.61 eq(s(z0), 0) -> false 322.24/291.61 eq(s(z0), s(z1)) -> eq(z0, z1) 322.24/291.61 rm(z0, nil) -> nil 322.24/291.61 rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2)) 322.24/291.61 ifrm(true, z0, add(z1, z2)) -> rm(z0, z2) 322.24/291.61 ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2)) 322.24/291.61 Tuples: 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 S tuples: 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 K tuples: 322.24/291.61 PURGE(add(z0, z1)) -> c9(PURGE(rm(z0, z1)), RM(z0, z1)) 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 Defined Rule Symbols: eq_2, rm_2, ifrm_3 322.24/291.61 322.24/291.61 Defined Pair Symbols: EQ_2, RM_2, IFRM_3, PURGE_1 322.24/291.61 322.24/291.61 Compound Symbols: c3_1, c5_2, c6_1, c7_1, c9_2 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (15) CdtKnowledgeProof (FINISHED) 322.24/291.61 The following tuples could be moved from S to K by knowledge propagation: 322.24/291.61 RM(z0, add(z1, z2)) -> c5(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1)) 322.24/291.61 IFRM(true, z0, add(z1, z2)) -> c6(RM(z0, z2)) 322.24/291.61 IFRM(false, z0, add(z1, z2)) -> c7(RM(z0, z2)) 322.24/291.61 EQ(s(z0), s(z1)) -> c3(EQ(z0, z1)) 322.24/291.61 Now S is empty 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (16) 322.24/291.61 BOUNDS(1, 1) 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 322.24/291.61 Transformed a relative TRS into a decreasing-loop problem. 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (18) 322.24/291.61 Obligation: 322.24/291.61 Analyzing the following TRS for decreasing loops: 322.24/291.61 322.24/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 322.24/291.61 322.24/291.61 322.24/291.61 The TRS R consists of the following rules: 322.24/291.61 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(X)) -> false 322.24/291.61 eq(s(X), 0) -> false 322.24/291.61 eq(s(X), s(Y)) -> eq(X, Y) 322.24/291.61 rm(N, nil) -> nil 322.24/291.61 rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X)) 322.24/291.61 ifrm(true, N, add(M, X)) -> rm(N, X) 322.24/291.61 ifrm(false, N, add(M, X)) -> add(M, rm(N, X)) 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(N, X)) -> add(N, purge(rm(N, X))) 322.24/291.61 322.24/291.61 S is empty. 322.24/291.61 Rewrite Strategy: INNERMOST 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (19) DecreasingLoopProof (LOWER BOUND(ID)) 322.24/291.61 The following loop(s) give(s) rise to the lower bound Omega(n^1): 322.24/291.61 322.24/291.61 The rewrite sequence 322.24/291.61 322.24/291.61 eq(s(X), s(Y)) ->^+ eq(X, Y) 322.24/291.61 322.24/291.61 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 322.24/291.61 322.24/291.61 The pumping substitution is [X / s(X), Y / s(Y)]. 322.24/291.61 322.24/291.61 The result substitution is [ ]. 322.24/291.61 322.24/291.61 322.24/291.61 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (20) 322.24/291.61 Complex Obligation (BEST) 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (21) 322.24/291.61 Obligation: 322.24/291.61 Proved the lower bound n^1 for the following obligation: 322.24/291.61 322.24/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 322.24/291.61 322.24/291.61 322.24/291.61 The TRS R consists of the following rules: 322.24/291.61 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(X)) -> false 322.24/291.61 eq(s(X), 0) -> false 322.24/291.61 eq(s(X), s(Y)) -> eq(X, Y) 322.24/291.61 rm(N, nil) -> nil 322.24/291.61 rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X)) 322.24/291.61 ifrm(true, N, add(M, X)) -> rm(N, X) 322.24/291.61 ifrm(false, N, add(M, X)) -> add(M, rm(N, X)) 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(N, X)) -> add(N, purge(rm(N, X))) 322.24/291.61 322.24/291.61 S is empty. 322.24/291.61 Rewrite Strategy: INNERMOST 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (22) LowerBoundPropagationProof (FINISHED) 322.24/291.61 Propagated lower bound. 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (23) 322.24/291.61 BOUNDS(n^1, INF) 322.24/291.61 322.24/291.61 ---------------------------------------- 322.24/291.61 322.24/291.61 (24) 322.24/291.61 Obligation: 322.24/291.61 Analyzing the following TRS for decreasing loops: 322.24/291.61 322.24/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 322.24/291.61 322.24/291.61 322.24/291.61 The TRS R consists of the following rules: 322.24/291.61 322.24/291.61 eq(0, 0) -> true 322.24/291.61 eq(0, s(X)) -> false 322.24/291.61 eq(s(X), 0) -> false 322.24/291.61 eq(s(X), s(Y)) -> eq(X, Y) 322.24/291.61 rm(N, nil) -> nil 322.24/291.61 rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X)) 322.24/291.61 ifrm(true, N, add(M, X)) -> rm(N, X) 322.24/291.61 ifrm(false, N, add(M, X)) -> add(M, rm(N, X)) 322.24/291.61 purge(nil) -> nil 322.24/291.61 purge(add(N, X)) -> add(N, purge(rm(N, X))) 322.24/291.61 322.24/291.61 S is empty. 322.24/291.61 Rewrite Strategy: INNERMOST 322.24/291.64 EOF