25.19/8.23 WORST_CASE(Omega(n^1), O(n^1)) 25.19/8.24 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 25.19/8.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.19/8.24 25.19/8.24 25.19/8.24 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.19/8.24 25.19/8.24 (0) CpxTRS 25.19/8.24 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 25.19/8.24 (2) CdtProblem 25.19/8.24 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 25.19/8.24 (4) CdtProblem 25.19/8.24 (5) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 123 ms] 25.19/8.24 (6) CdtProblem 25.19/8.24 (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 25.19/8.24 (8) CdtProblem 25.19/8.24 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 38 ms] 25.19/8.24 (10) CdtProblem 25.19/8.24 (11) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 25.19/8.24 (12) CdtProblem 25.19/8.24 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 29 ms] 25.19/8.24 (14) CdtProblem 25.19/8.24 (15) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 25.19/8.24 (16) CdtProblem 25.19/8.24 (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 24 ms] 25.19/8.24 (18) CdtProblem 25.19/8.24 (19) CdtKnowledgeProof [FINISHED, 0 ms] 25.19/8.24 (20) BOUNDS(1, 1) 25.19/8.24 (21) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 25.19/8.24 (22) TRS for Loop Detection 25.19/8.24 (23) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 25.19/8.24 (24) BEST 25.19/8.24 (25) proven lower bound 25.19/8.24 (26) LowerBoundPropagationProof [FINISHED, 0 ms] 25.19/8.24 (27) BOUNDS(n^1, INF) 25.19/8.24 (28) TRS for Loop Detection 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (0) 25.19/8.24 Obligation: 25.19/8.24 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.19/8.24 25.19/8.24 25.19/8.24 The TRS R consists of the following rules: 25.19/8.24 25.19/8.24 append(@l1, @l2) -> append#1(@l1, @l2) 25.19/8.24 append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) 25.19/8.24 append#1(nil, @l2) -> @l2 25.19/8.24 appendAll(@l) -> appendAll#1(@l) 25.19/8.24 appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(@l) -> appendAll2#1(@l) 25.19/8.24 appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(@l) -> appendAll3#1(@l) 25.19/8.24 appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 25.19/8.24 S is empty. 25.19/8.24 Rewrite Strategy: INNERMOST 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 25.19/8.24 Converted Cpx (relative) TRS to CDT 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (2) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPEND#1(nil, z0) -> c2 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL#1(nil) -> c5 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2#1(nil) -> c8 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL3#1(nil) -> c11 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPEND#1(nil, z0) -> c2 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL#1(nil) -> c5 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2#1(nil) -> c8 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL3#1(nil) -> c11 25.19/8.24 K tuples:none 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c2, c3_1, c4_2, c5, c6_1, c7_3, c8, c9_1, c10_3, c11 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 25.19/8.24 Removed 4 trailing nodes: 25.19/8.24 APPEND#1(nil, z0) -> c2 25.19/8.24 APPENDALL#1(nil) -> c5 25.19/8.24 APPENDALL3#1(nil) -> c11 25.19/8.24 APPENDALL2#1(nil) -> c8 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (4) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 K tuples:none 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (5) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.19/8.24 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 We considered the (Usable) Rules:none 25.19/8.24 And the Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 The order we found is given by the following interpretation: 25.19/8.24 25.19/8.24 Polynomial interpretation : 25.19/8.24 25.19/8.24 POL(::(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(APPEND(x_1, x_2)) = 0 25.19/8.24 POL(APPEND#1(x_1, x_2)) = 0 25.19/8.24 POL(APPENDALL(x_1)) = 0 25.19/8.24 POL(APPENDALL#1(x_1)) = 0 25.19/8.24 POL(APPENDALL2(x_1)) = 0 25.19/8.24 POL(APPENDALL2#1(x_1)) = 0 25.19/8.24 POL(APPENDALL3(x_1)) = [1] + x_1 25.19/8.24 POL(APPENDALL3#1(x_1)) = x_1 25.19/8.24 POL(append(x_1, x_2)) = 0 25.19/8.24 POL(append#1(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(appendAll(x_1)) = x_1 25.19/8.24 POL(appendAll#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll2(x_1)) = x_1 25.19/8.24 POL(appendAll2#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3#1(x_1)) = [1] + x_1 25.19/8.24 POL(c(x_1)) = x_1 25.19/8.24 POL(c1(x_1)) = x_1 25.19/8.24 POL(c10(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c3(x_1)) = x_1 25.19/8.24 POL(c4(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(c6(x_1)) = x_1 25.19/8.24 POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c9(x_1)) = x_1 25.19/8.24 POL(nil) = [1] 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (6) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 25.19/8.24 The following tuples could be moved from S to K by knowledge propagation: 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (8) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.19/8.24 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 We considered the (Usable) Rules:none 25.19/8.24 And the Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 The order we found is given by the following interpretation: 25.19/8.24 25.19/8.24 Polynomial interpretation : 25.19/8.24 25.19/8.24 POL(::(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(APPEND(x_1, x_2)) = 0 25.19/8.24 POL(APPEND#1(x_1, x_2)) = 0 25.19/8.24 POL(APPENDALL(x_1)) = 0 25.19/8.24 POL(APPENDALL#1(x_1)) = 0 25.19/8.24 POL(APPENDALL2(x_1)) = x_1 25.19/8.24 POL(APPENDALL2#1(x_1)) = x_1 25.19/8.24 POL(APPENDALL3(x_1)) = [1] + x_1 25.19/8.24 POL(APPENDALL3#1(x_1)) = [1] + x_1 25.19/8.24 POL(append(x_1, x_2)) = 0 25.19/8.24 POL(append#1(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(appendAll(x_1)) = x_1 25.19/8.24 POL(appendAll#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll2(x_1)) = x_1 25.19/8.24 POL(appendAll2#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3#1(x_1)) = [1] + x_1 25.19/8.24 POL(c(x_1)) = x_1 25.19/8.24 POL(c1(x_1)) = x_1 25.19/8.24 POL(c10(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c3(x_1)) = x_1 25.19/8.24 POL(c4(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(c6(x_1)) = x_1 25.19/8.24 POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c9(x_1)) = x_1 25.19/8.24 POL(nil) = [1] 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (10) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (11) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 25.19/8.24 The following tuples could be moved from S to K by knowledge propagation: 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (12) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.19/8.24 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 We considered the (Usable) Rules:none 25.19/8.24 And the Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 The order we found is given by the following interpretation: 25.19/8.24 25.19/8.24 Polynomial interpretation : 25.19/8.24 25.19/8.24 POL(::(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(APPEND(x_1, x_2)) = 0 25.19/8.24 POL(APPEND#1(x_1, x_2)) = 0 25.19/8.24 POL(APPENDALL(x_1)) = x_1 25.19/8.24 POL(APPENDALL#1(x_1)) = x_1 25.19/8.24 POL(APPENDALL2(x_1)) = x_1 25.19/8.24 POL(APPENDALL2#1(x_1)) = x_1 25.19/8.24 POL(APPENDALL3(x_1)) = x_1 25.19/8.24 POL(APPENDALL3#1(x_1)) = x_1 25.19/8.24 POL(append(x_1, x_2)) = 0 25.19/8.24 POL(append#1(x_1, x_2)) = [1] + x_1 + x_2 25.19/8.24 POL(appendAll(x_1)) = x_1 25.19/8.24 POL(appendAll#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll2(x_1)) = x_1 25.19/8.24 POL(appendAll2#1(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3(x_1)) = [1] + x_1 25.19/8.24 POL(appendAll3#1(x_1)) = [1] + x_1 25.19/8.24 POL(c(x_1)) = x_1 25.19/8.24 POL(c1(x_1)) = x_1 25.19/8.24 POL(c10(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c3(x_1)) = x_1 25.19/8.24 POL(c4(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(c6(x_1)) = x_1 25.19/8.24 POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c9(x_1)) = x_1 25.19/8.24 POL(nil) = [1] 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (14) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (15) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 25.19/8.24 The following tuples could be moved from S to K by knowledge propagation: 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (16) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.19/8.24 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 We considered the (Usable) Rules: 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 And the Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 The order we found is given by the following interpretation: 25.19/8.24 25.19/8.24 Polynomial interpretation : 25.19/8.24 25.19/8.24 POL(::(x_1, x_2)) = [2] + x_1 + x_2 25.19/8.24 POL(APPEND(x_1, x_2)) = x_1 25.19/8.24 POL(APPEND#1(x_1, x_2)) = x_1 25.19/8.24 POL(APPENDALL(x_1)) = x_1 25.19/8.24 POL(APPENDALL#1(x_1)) = x_1 25.19/8.24 POL(APPENDALL2(x_1)) = [2]x_1 25.19/8.24 POL(APPENDALL2#1(x_1)) = [2]x_1 25.19/8.24 POL(APPENDALL3(x_1)) = [2] + [3]x_1 25.19/8.24 POL(APPENDALL3#1(x_1)) = [2] + [3]x_1 25.19/8.24 POL(append(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(append#1(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(appendAll(x_1)) = x_1 25.19/8.24 POL(appendAll#1(x_1)) = x_1 25.19/8.24 POL(appendAll2(x_1)) = x_1 25.19/8.24 POL(appendAll2#1(x_1)) = x_1 25.19/8.24 POL(appendAll3(x_1)) = [3] + [3]x_1 25.19/8.24 POL(appendAll3#1(x_1)) = [3] + [3]x_1 25.19/8.24 POL(c(x_1)) = x_1 25.19/8.24 POL(c1(x_1)) = x_1 25.19/8.24 POL(c10(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c3(x_1)) = x_1 25.19/8.24 POL(c4(x_1, x_2)) = x_1 + x_2 25.19/8.24 POL(c6(x_1)) = x_1 25.19/8.24 POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.19/8.24 POL(c9(x_1)) = x_1 25.19/8.24 POL(nil) = 0 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (18) 25.19/8.24 Obligation: 25.19/8.24 Complexity Dependency Tuples Problem 25.19/8.24 25.19/8.24 Rules: 25.19/8.24 append(z0, z1) -> append#1(z0, z1) 25.19/8.24 append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2)) 25.19/8.24 append#1(nil, z0) -> z0 25.19/8.24 appendAll(z0) -> appendAll#1(z0) 25.19/8.24 appendAll#1(::(z0, z1)) -> append(z0, appendAll(z1)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(z0) -> appendAll2#1(z0) 25.19/8.24 appendAll2#1(::(z0, z1)) -> append(appendAll(z0), appendAll2(z1)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(z0) -> appendAll3#1(z0) 25.19/8.24 appendAll3#1(::(z0, z1)) -> append(appendAll2(z0), appendAll3(z1)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 Tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 S tuples: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 K tuples: 25.19/8.24 APPENDALL3(z0) -> c9(APPENDALL3#1(z0)) 25.19/8.24 APPENDALL3#1(::(z0, z1)) -> c10(APPEND(appendAll2(z0), appendAll3(z1)), APPENDALL2(z0), APPENDALL3(z1)) 25.19/8.24 APPENDALL2#1(::(z0, z1)) -> c7(APPEND(appendAll(z0), appendAll2(z1)), APPENDALL(z0), APPENDALL2(z1)) 25.19/8.24 APPENDALL2(z0) -> c6(APPENDALL2#1(z0)) 25.19/8.24 APPENDALL#1(::(z0, z1)) -> c4(APPEND(z0, appendAll(z1)), APPENDALL(z1)) 25.19/8.24 APPENDALL(z0) -> c3(APPENDALL#1(z0)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 Defined Rule Symbols: append_2, append#1_2, appendAll_1, appendAll#1_1, appendAll2_1, appendAll2#1_1, appendAll3_1, appendAll3#1_1 25.19/8.24 25.19/8.24 Defined Pair Symbols: APPEND_2, APPEND#1_2, APPENDALL_1, APPENDALL#1_1, APPENDALL2_1, APPENDALL2#1_1, APPENDALL3_1, APPENDALL3#1_1 25.19/8.24 25.19/8.24 Compound Symbols: c_1, c1_1, c3_1, c4_2, c6_1, c7_3, c9_1, c10_3 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (19) CdtKnowledgeProof (FINISHED) 25.19/8.24 The following tuples could be moved from S to K by knowledge propagation: 25.19/8.24 APPEND(z0, z1) -> c(APPEND#1(z0, z1)) 25.19/8.24 APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2)) 25.19/8.24 Now S is empty 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (20) 25.19/8.24 BOUNDS(1, 1) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (21) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 25.19/8.24 Transformed a relative TRS into a decreasing-loop problem. 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (22) 25.19/8.24 Obligation: 25.19/8.24 Analyzing the following TRS for decreasing loops: 25.19/8.24 25.19/8.24 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.19/8.24 25.19/8.24 25.19/8.24 The TRS R consists of the following rules: 25.19/8.24 25.19/8.24 append(@l1, @l2) -> append#1(@l1, @l2) 25.19/8.24 append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) 25.19/8.24 append#1(nil, @l2) -> @l2 25.19/8.24 appendAll(@l) -> appendAll#1(@l) 25.19/8.24 appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(@l) -> appendAll2#1(@l) 25.19/8.24 appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(@l) -> appendAll3#1(@l) 25.19/8.24 appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 25.19/8.24 S is empty. 25.19/8.24 Rewrite Strategy: INNERMOST 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (23) DecreasingLoopProof (LOWER BOUND(ID)) 25.19/8.24 The following loop(s) give(s) rise to the lower bound Omega(n^1): 25.19/8.24 25.19/8.24 The rewrite sequence 25.19/8.24 25.19/8.24 appendAll#1(::(@l1, @ls)) ->^+ append(@l1, appendAll#1(@ls)) 25.19/8.24 25.19/8.24 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 25.19/8.24 25.19/8.24 The pumping substitution is [@ls / ::(@l1, @ls)]. 25.19/8.24 25.19/8.24 The result substitution is [ ]. 25.19/8.24 25.19/8.24 25.19/8.24 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (24) 25.19/8.24 Complex Obligation (BEST) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (25) 25.19/8.24 Obligation: 25.19/8.24 Proved the lower bound n^1 for the following obligation: 25.19/8.24 25.19/8.24 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.19/8.24 25.19/8.24 25.19/8.24 The TRS R consists of the following rules: 25.19/8.24 25.19/8.24 append(@l1, @l2) -> append#1(@l1, @l2) 25.19/8.24 append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) 25.19/8.24 append#1(nil, @l2) -> @l2 25.19/8.24 appendAll(@l) -> appendAll#1(@l) 25.19/8.24 appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(@l) -> appendAll2#1(@l) 25.19/8.24 appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(@l) -> appendAll3#1(@l) 25.19/8.24 appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 25.19/8.24 S is empty. 25.19/8.24 Rewrite Strategy: INNERMOST 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (26) LowerBoundPropagationProof (FINISHED) 25.19/8.24 Propagated lower bound. 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (27) 25.19/8.24 BOUNDS(n^1, INF) 25.19/8.24 25.19/8.24 ---------------------------------------- 25.19/8.24 25.19/8.24 (28) 25.19/8.24 Obligation: 25.19/8.24 Analyzing the following TRS for decreasing loops: 25.19/8.24 25.19/8.24 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.19/8.24 25.19/8.24 25.19/8.24 The TRS R consists of the following rules: 25.19/8.24 25.19/8.24 append(@l1, @l2) -> append#1(@l1, @l2) 25.19/8.24 append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) 25.19/8.24 append#1(nil, @l2) -> @l2 25.19/8.24 appendAll(@l) -> appendAll#1(@l) 25.19/8.24 appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) 25.19/8.24 appendAll#1(nil) -> nil 25.19/8.24 appendAll2(@l) -> appendAll2#1(@l) 25.19/8.24 appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) 25.19/8.24 appendAll2#1(nil) -> nil 25.19/8.24 appendAll3(@l) -> appendAll3#1(@l) 25.19/8.24 appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) 25.19/8.24 appendAll3#1(nil) -> nil 25.19/8.24 25.19/8.24 S is empty. 25.19/8.24 Rewrite Strategy: INNERMOST 25.33/8.31 EOF