8.43/2.85 YES 8.43/2.86 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.43/2.86 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.43/2.86 8.43/2.86 8.43/2.86 Termination of the given CSR could be proven: 8.43/2.86 8.43/2.86 (0) CSR 8.43/2.86 (1) CSRRRRProof [EQUIVALENT, 84 ms] 8.43/2.86 (2) CSR 8.43/2.86 (3) CSRRRRProof [EQUIVALENT, 29 ms] 8.43/2.86 (4) CSR 8.43/2.86 (5) CSRRRRProof [EQUIVALENT, 0 ms] 8.43/2.86 (6) CSR 8.43/2.86 (7) CSRRRRProof [EQUIVALENT, 13 ms] 8.43/2.86 (8) CSR 8.43/2.86 (9) CSRRRRProof [EQUIVALENT, 131 ms] 8.43/2.86 (10) CSR 8.43/2.86 (11) CSRRRRProof [EQUIVALENT, 118 ms] 8.43/2.86 (12) CSR 8.43/2.86 (13) CSRRRRProof [EQUIVALENT, 126 ms] 8.43/2.86 (14) CSR 8.43/2.86 (15) CSRRRRProof [EQUIVALENT, 53 ms] 8.43/2.86 (16) CSR 8.43/2.86 (17) CSRRRRProof [EQUIVALENT, 15 ms] 8.43/2.86 (18) CSR 8.43/2.86 (19) CSRRRRProof [EQUIVALENT, 0 ms] 8.43/2.86 (20) CSR 8.43/2.86 (21) CSRRRRProof [EQUIVALENT, 0 ms] 8.43/2.86 (22) CSR 8.43/2.86 (23) CSRRRRProof [EQUIVALENT, 0 ms] 8.43/2.86 (24) CSR 8.43/2.86 (25) RisEmptyProof [EQUIVALENT, 0 ms] 8.43/2.86 (26) YES 8.43/2.86 8.43/2.86 8.43/2.86 ---------------------------------------- 8.43/2.86 8.43/2.86 (0) 8.43/2.86 Obligation: 8.43/2.86 Context-sensitive rewrite system: 8.43/2.86 The TRS R consists of the following rules: 8.43/2.86 8.43/2.86 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.86 tail_1(cons_2(x, s)) -> s 8.43/2.86 tail_1(cons_3(x, s)) -> s 8.43/2.86 tail_1(cons_4(x, s)) -> s 8.43/2.86 *top*_0(tail_1(cons_5(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_5(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_5(x, s))) -> tail_1(s) 8.43/2.86 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.86 tail_1(cons_7(x, s)) -> s 8.43/2.86 tail_1(cons_8(x, s)) -> s 8.43/2.86 tail_1(cons_9(x, s)) -> s 8.43/2.86 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.86 *top*_0(tail_1(cons_11(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_11(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_11(x, s))) -> tail_1(s) 8.43/2.86 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.86 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.86 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.86 tail_1(cons_1(x, s)) -> s 8.43/2.86 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_3(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_3(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_3(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_4(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_4(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_4(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_5(0_0, s))) -> *top*_0(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.86 h_0(h_1(cons_5(0_0, s))) -> h_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.86 tail_0(h_1(cons_5(0_0, s))) -> tail_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.86 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.86 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.86 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.86 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_7(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_7(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_7(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_9(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_9(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_9(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.86 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.86 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.86 *top*_0(h_1(cons_11(1_0, s))) -> *top*_0(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.86 h_0(h_1(cons_11(1_0, s))) -> h_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.86 tail_0(h_1(cons_11(1_0, s))) -> tail_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.86 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.86 cons_2(x, s) -> garbage_collection_0 8.43/2.86 cons_3(x, s) -> garbage_collection_0 8.43/2.86 cons_4(x, s) -> garbage_collection_0 8.43/2.86 cons_5(x, s) -> garbage_collection_0 8.43/2.86 cons_6(x, s) -> garbage_collection_0 8.43/2.86 cons_7(x, s) -> garbage_collection_0 8.43/2.86 cons_8(x, s) -> garbage_collection_0 8.43/2.86 cons_9(x, s) -> garbage_collection_0 8.43/2.86 cons_10(x, s) -> garbage_collection_0 8.43/2.86 cons_11(x, s) -> garbage_collection_0 8.43/2.86 cons_1(x, s) -> garbage_collection_0 8.43/2.86 8.43/2.86 The replacement map contains the following entries: 8.43/2.86 8.43/2.86 M_1: empty set 8.43/2.86 h_1: empty set 8.43/2.86 cons_1: empty set 8.43/2.86 0_0: empty set 8.43/2.86 tail_0: {1} 8.43/2.86 tail_1: empty set 8.43/2.86 cons_2: empty set 8.43/2.86 cons_3: empty set 8.43/2.86 cons_4: empty set 8.43/2.86 *top*_0: {1} 8.43/2.86 cons_5: empty set 8.43/2.86 h_0: {1} 8.43/2.86 cons_6: empty set 8.43/2.86 cons_7: empty set 8.43/2.86 cons_8: empty set 8.43/2.86 cons_9: empty set 8.43/2.86 cons_10: empty set 8.43/2.86 cons_11: empty set 8.43/2.86 1_0: empty set 8.43/2.86 garbage_collection_0: empty set 8.43/2.86 8.43/2.86 ---------------------------------------- 8.43/2.86 8.43/2.86 (1) CSRRRRProof (EQUIVALENT) 8.43/2.86 The following CSR is given: Context-sensitive rewrite system: 8.43/2.86 The TRS R consists of the following rules: 8.43/2.86 8.43/2.86 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.86 tail_1(cons_2(x, s)) -> s 8.43/2.86 tail_1(cons_3(x, s)) -> s 8.43/2.86 tail_1(cons_4(x, s)) -> s 8.43/2.86 *top*_0(tail_1(cons_5(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_5(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_5(x, s))) -> tail_1(s) 8.43/2.86 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.86 tail_1(cons_7(x, s)) -> s 8.43/2.86 tail_1(cons_8(x, s)) -> s 8.43/2.86 tail_1(cons_9(x, s)) -> s 8.43/2.86 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.86 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.86 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.87 *top*_0(tail_1(cons_11(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_11(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_11(x, s))) -> tail_1(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.87 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.87 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.87 tail_1(cons_1(x, s)) -> s 8.43/2.87 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_3(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_3(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_3(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_4(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_4(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_4(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_5(0_0, s))) -> *top*_0(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_5(0_0, s))) -> h_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_5(0_0, s))) -> tail_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_7(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_7(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_7(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_9(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_9(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_9(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_11(1_0, s))) -> *top*_0(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_11(1_0, s))) -> h_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_11(1_0, s))) -> tail_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 cons_2(x, s) -> garbage_collection_0 8.43/2.87 cons_3(x, s) -> garbage_collection_0 8.43/2.87 cons_4(x, s) -> garbage_collection_0 8.43/2.87 cons_5(x, s) -> garbage_collection_0 8.43/2.87 cons_6(x, s) -> garbage_collection_0 8.43/2.87 cons_7(x, s) -> garbage_collection_0 8.43/2.87 cons_8(x, s) -> garbage_collection_0 8.43/2.87 cons_9(x, s) -> garbage_collection_0 8.43/2.87 cons_10(x, s) -> garbage_collection_0 8.43/2.87 cons_11(x, s) -> garbage_collection_0 8.43/2.87 cons_1(x, s) -> garbage_collection_0 8.43/2.87 8.43/2.87 The replacement map contains the following entries: 8.43/2.87 8.43/2.87 M_1: empty set 8.43/2.87 h_1: empty set 8.43/2.87 cons_1: empty set 8.43/2.87 0_0: empty set 8.43/2.87 tail_0: {1} 8.43/2.87 tail_1: empty set 8.43/2.87 cons_2: empty set 8.43/2.87 cons_3: empty set 8.43/2.87 cons_4: empty set 8.43/2.87 *top*_0: {1} 8.43/2.87 cons_5: empty set 8.43/2.87 h_0: {1} 8.43/2.87 cons_6: empty set 8.43/2.87 cons_7: empty set 8.43/2.87 cons_8: empty set 8.43/2.87 cons_9: empty set 8.43/2.87 cons_10: empty set 8.43/2.87 cons_11: empty set 8.43/2.87 1_0: empty set 8.43/2.87 garbage_collection_0: empty set 8.43/2.87 Used ordering: 8.43/2.87 Polynomial interpretation [POLO]: 8.43/2.87 8.43/2.87 POL(*top*_0(x_1)) = x_1 8.43/2.87 POL(0_0) = 1 8.43/2.87 POL(1_0) = 1 8.43/2.87 POL(M_1) = 0 8.43/2.87 POL(cons_1(x_1, x_2)) = x_2 8.43/2.87 POL(cons_10(x_1, x_2)) = x_2 8.43/2.87 POL(cons_11(x_1, x_2)) = 1 + x_1 + x_2 8.43/2.87 POL(cons_2(x_1, x_2)) = x_2 8.43/2.87 POL(cons_3(x_1, x_2)) = x_1 + x_2 8.43/2.87 POL(cons_4(x_1, x_2)) = x_1 + x_2 8.43/2.87 POL(cons_5(x_1, x_2)) = 1 + x_1 + x_2 8.43/2.87 POL(cons_6(x_1, x_2)) = x_2 8.43/2.87 POL(cons_7(x_1, x_2)) = x_1 + x_2 8.43/2.87 POL(cons_8(x_1, x_2)) = x_2 8.43/2.87 POL(cons_9(x_1, x_2)) = x_1 + x_2 8.43/2.87 POL(garbage_collection_0) = 0 8.43/2.87 POL(h_0(x_1)) = x_1 8.43/2.87 POL(h_1(x_1)) = x_1 8.43/2.87 POL(tail_0(x_1)) = x_1 8.43/2.87 POL(tail_1(x_1)) = x_1 8.43/2.87 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.87 8.43/2.87 *top*_0(tail_1(cons_5(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_5(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_5(x, s))) -> tail_1(s) 8.43/2.87 *top*_0(tail_1(cons_11(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_11(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_11(x, s))) -> tail_1(s) 8.43/2.87 *top*_0(h_1(cons_3(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_3(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_3(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_4(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_4(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_4(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_5(0_0, s))) -> *top*_0(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_5(0_0, s))) -> h_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_5(0_0, s))) -> tail_1(cons_6(0_0, cons_7(1_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_7(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_7(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_7(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_9(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_9(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_9(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_11(1_0, s))) -> *top*_0(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_11(1_0, s))) -> h_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_11(1_0, s))) -> tail_1(cons_10(1_0, cons_3(0_0, h_1(s)))) 8.43/2.87 cons_5(x, s) -> garbage_collection_0 8.43/2.87 cons_11(x, s) -> garbage_collection_0 8.43/2.87 8.43/2.87 8.43/2.87 8.43/2.87 8.43/2.87 ---------------------------------------- 8.43/2.87 8.43/2.87 (2) 8.43/2.87 Obligation: 8.43/2.87 Context-sensitive rewrite system: 8.43/2.87 The TRS R consists of the following rules: 8.43/2.87 8.43/2.87 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.87 tail_1(cons_2(x, s)) -> s 8.43/2.87 tail_1(cons_3(x, s)) -> s 8.43/2.87 tail_1(cons_4(x, s)) -> s 8.43/2.87 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.87 tail_1(cons_7(x, s)) -> s 8.43/2.87 tail_1(cons_8(x, s)) -> s 8.43/2.87 tail_1(cons_9(x, s)) -> s 8.43/2.87 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.87 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.87 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.87 tail_1(cons_1(x, s)) -> s 8.43/2.87 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.87 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.87 cons_2(x, s) -> garbage_collection_0 8.43/2.87 cons_3(x, s) -> garbage_collection_0 8.43/2.87 cons_4(x, s) -> garbage_collection_0 8.43/2.87 cons_6(x, s) -> garbage_collection_0 8.43/2.87 cons_7(x, s) -> garbage_collection_0 8.43/2.87 cons_8(x, s) -> garbage_collection_0 8.43/2.87 cons_9(x, s) -> garbage_collection_0 8.43/2.87 cons_10(x, s) -> garbage_collection_0 8.43/2.87 cons_1(x, s) -> garbage_collection_0 8.43/2.87 8.43/2.87 The replacement map contains the following entries: 8.43/2.87 8.43/2.87 M_1: empty set 8.43/2.87 h_1: empty set 8.43/2.87 cons_1: empty set 8.43/2.87 0_0: empty set 8.43/2.87 tail_0: {1} 8.43/2.87 tail_1: empty set 8.43/2.87 cons_2: empty set 8.43/2.87 cons_3: empty set 8.43/2.87 cons_4: empty set 8.43/2.87 *top*_0: {1} 8.43/2.87 h_0: {1} 8.43/2.87 cons_6: empty set 8.43/2.87 cons_7: empty set 8.43/2.87 cons_8: empty set 8.43/2.87 cons_9: empty set 8.43/2.87 cons_10: empty set 8.43/2.87 1_0: empty set 8.43/2.87 garbage_collection_0: empty set 8.43/2.87 8.43/2.87 ---------------------------------------- 8.43/2.87 8.43/2.87 (3) CSRRRRProof (EQUIVALENT) 8.43/2.87 The following CSR is given: Context-sensitive rewrite system: 8.43/2.87 The TRS R consists of the following rules: 8.43/2.87 8.43/2.87 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.87 tail_1(cons_2(x, s)) -> s 8.43/2.87 tail_1(cons_3(x, s)) -> s 8.43/2.87 tail_1(cons_4(x, s)) -> s 8.43/2.87 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.87 tail_1(cons_7(x, s)) -> s 8.43/2.87 tail_1(cons_8(x, s)) -> s 8.43/2.87 tail_1(cons_9(x, s)) -> s 8.43/2.87 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.87 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.87 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.87 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.87 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.87 tail_1(cons_1(x, s)) -> s 8.43/2.87 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.87 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 cons_4(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_7(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_9(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_3: empty set 8.43/2.88 cons_4: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_7: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_9: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(*top*_0(x_1)) = x_1 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(1_0) = 0 8.43/2.88 POL(M_1) = 0 8.43/2.88 POL(cons_1(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_10(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_2(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_3(x_1, x_2)) = x_2 8.43/2.88 POL(cons_4(x_1, x_2)) = x_2 8.43/2.88 POL(cons_6(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_7(x_1, x_2)) = 1 + x_2 8.43/2.88 POL(cons_8(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_9(x_1, x_2)) = 1 + x_2 8.43/2.88 POL(garbage_collection_0) = 0 8.43/2.88 POL(h_0(x_1)) = x_1 8.43/2.88 POL(h_1(x_1)) = x_1 8.43/2.88 POL(tail_0(x_1)) = x_1 8.43/2.88 POL(tail_1(x_1)) = x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_1(cons_7(x, s)) -> s 8.43/2.88 tail_1(cons_9(x, s)) -> s 8.43/2.88 cons_7(x, s) -> garbage_collection_0 8.43/2.88 cons_9(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (4) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 tail_1(cons_3(x, s)) -> s 8.43/2.88 tail_1(cons_4(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 cons_4(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_3: empty set 8.43/2.88 cons_4: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (5) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 tail_1(cons_3(x, s)) -> s 8.43/2.88 tail_1(cons_4(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 cons_4(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_3: empty set 8.43/2.88 cons_4: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(*top*_0(x_1)) = x_1 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(1_0) = 0 8.43/2.88 POL(M_1) = 0 8.43/2.88 POL(cons_1(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_10(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_2(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_3(x_1, x_2)) = x_2 8.43/2.88 POL(cons_4(x_1, x_2)) = 1 + x_2 8.43/2.88 POL(cons_6(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(cons_8(x_1, x_2)) = x_1 + x_2 8.43/2.88 POL(garbage_collection_0) = 0 8.43/2.88 POL(h_0(x_1)) = x_1 8.43/2.88 POL(h_1(x_1)) = x_1 8.43/2.88 POL(tail_0(x_1)) = x_1 8.43/2.88 POL(tail_1(x_1)) = x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_1(cons_4(x, s)) -> s 8.43/2.88 cons_4(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (6) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 tail_1(cons_3(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_3: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (7) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 tail_1(cons_3(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_3: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(*top*_0(x_1)) = x_1 8.43/2.88 POL(0_0) = 1 8.43/2.88 POL(1_0) = 1 8.43/2.88 POL(M_1) = 0 8.43/2.88 POL(cons_1(x_1, x_2)) = x_2 8.43/2.88 POL(cons_10(x_1, x_2)) = x_2 8.43/2.88 POL(cons_2(x_1, x_2)) = x_2 8.43/2.88 POL(cons_3(x_1, x_2)) = 1 + x_2 8.43/2.88 POL(cons_6(x_1, x_2)) = x_2 8.43/2.88 POL(cons_8(x_1, x_2)) = x_2 8.43/2.88 POL(garbage_collection_0) = 0 8.43/2.88 POL(h_0(x_1)) = x_1 8.43/2.88 POL(h_1(x_1)) = x_1 8.43/2.88 POL(tail_0(x_1)) = x_1 8.43/2.88 POL(tail_1(x_1)) = x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_1(cons_3(x, s)) -> s 8.43/2.88 cons_3(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (8) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (9) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(M_1) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_1(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_1(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(0_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_0(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_1(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_2(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(*top*_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_6(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_8(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_10(x_1, x_2)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(1_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(garbage_collection_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_0(tail_1(cons_10(x, s))) -> tail_1(s) 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (10) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (11) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(M_1) = [[0], [1]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_1(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_1(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(0_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_0(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_1(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_2(x_1, x_2)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(*top*_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_6(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_8(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_10(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(1_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(garbage_collection_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_1(cons_2(x, s)) -> s 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (12) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (13) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(M_1) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_1(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_1(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(0_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_0(x_1)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(*top*_0(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_1(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_6(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_8(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_10(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_2(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(1_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(garbage_collection_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 *top*_0(tail_1(cons_6(x, s))) -> *top*_0(s) 8.43/2.88 *top*_0(tail_1(cons_10(x, s))) -> *top*_0(s) 8.43/2.88 *top*_0(tail_1(cons_1(x, s))) -> *top*_0(s) 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (14) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (15) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(M_1) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_1(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_1(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(0_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_0(x_1)) = [[0], [1]] + [[1, 1], [0, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(h_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(tail_1(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_6(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_8(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_10(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(*top*_0(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(cons_2(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(1_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 <<< 8.43/2.88 POL(garbage_collection_0) = [[0], [0]] 8.43/2.88 >>> 8.43/2.88 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_0(tail_1(cons_6(x, s))) -> tail_1(s) 8.43/2.88 tail_0(tail_1(cons_1(x, s))) -> tail_1(s) 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (16) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (17) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 *top*_0: {1} 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 1_0: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(*top*_0(x_1)) = x_1 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(1_0) = 0 8.43/2.88 POL(M_1) = 1 8.43/2.88 POL(cons_1(x_1, x_2)) = 1 + x_2 8.43/2.88 POL(cons_10(x_1, x_2)) = 0 8.43/2.88 POL(cons_2(x_1, x_2)) = x_2 8.43/2.88 POL(cons_6(x_1, x_2)) = 0 8.43/2.88 POL(cons_8(x_1, x_2)) = x_2 8.43/2.88 POL(garbage_collection_0) = 0 8.43/2.88 POL(h_0(x_1)) = 1 + x_1 8.43/2.88 POL(h_1(x_1)) = 1 8.43/2.88 POL(tail_0(x_1)) = x_1 8.43/2.88 POL(tail_1(x_1)) = x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_1(x, s))) -> h_0(s) 8.43/2.88 tail_1(cons_1(x, s)) -> s 8.43/2.88 *top*_0(h_1(cons_2(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_2(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_2(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_6(0_0, s))) -> *top*_0(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_6(0_0, s))) -> h_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_6(0_0, s))) -> tail_1(cons_6(0_0, cons_8(1_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(0_0, s))) -> *top*_0(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(0_0, s))) -> h_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(0_0, s))) -> tail_1(cons_6(0_0, cons_1(1_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_8(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_8(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_8(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 *top*_0(h_1(cons_10(1_0, s))) -> *top*_0(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 h_0(h_1(cons_10(1_0, s))) -> h_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 tail_0(h_1(cons_10(1_0, s))) -> tail_1(cons_10(1_0, cons_2(0_0, h_1(s)))) 8.43/2.88 *top*_0(h_1(cons_1(1_0, s))) -> *top*_0(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 h_0(h_1(cons_1(1_0, s))) -> h_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 tail_0(h_1(cons_1(1_0, s))) -> tail_1(cons_10(1_0, cons_1(0_0, h_0(s)))) 8.43/2.88 cons_1(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (18) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (19) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 h_0: {1} 8.43/2.88 cons_6: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 cons_10: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(M_1) = 0 8.43/2.88 POL(cons_1(x_1, x_2)) = 2 + 2*x_1 8.43/2.88 POL(cons_10(x_1, x_2)) = 2 8.43/2.88 POL(cons_2(x_1, x_2)) = 0 8.43/2.88 POL(cons_6(x_1, x_2)) = 2 8.43/2.88 POL(cons_8(x_1, x_2)) = x_2 8.43/2.88 POL(garbage_collection_0) = 0 8.43/2.88 POL(h_0(x_1)) = x_1 8.43/2.88 POL(h_1(x_1)) = 0 8.43/2.88 POL(tail_0(x_1)) = 2*x_1 8.43/2.88 POL(tail_1(x_1)) = x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 h_0(tail_1(cons_6(x, s))) -> h_1(s) 8.43/2.88 h_0(tail_1(cons_10(x, s))) -> h_1(s) 8.43/2.88 cons_6(x, s) -> garbage_collection_0 8.43/2.88 cons_10(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (20) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (21) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 tail_1: empty set 8.43/2.88 cons_2: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(M_1) = 0 8.43/2.88 POL(cons_1(x_1, x_2)) = 2 + 2*x_1 8.43/2.88 POL(cons_2(x_1, x_2)) = 2 8.43/2.88 POL(cons_8(x_1, x_2)) = 2 + x_2 8.43/2.88 POL(garbage_collection_0) = 2 8.43/2.88 POL(h_1(x_1)) = 0 8.43/2.88 POL(tail_0(x_1)) = 2*x_1 8.43/2.88 POL(tail_1(x_1)) = 2*x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 tail_1(cons_8(x, s)) -> s 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (22) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 cons_2: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (23) CSRRRRProof (EQUIVALENT) 8.43/2.88 The following CSR is given: Context-sensitive rewrite system: 8.43/2.88 The TRS R consists of the following rules: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 The replacement map contains the following entries: 8.43/2.88 8.43/2.88 M_1: empty set 8.43/2.88 h_1: empty set 8.43/2.88 cons_1: empty set 8.43/2.88 0_0: empty set 8.43/2.88 tail_0: {1} 8.43/2.88 cons_2: empty set 8.43/2.88 cons_8: empty set 8.43/2.88 garbage_collection_0: empty set 8.43/2.88 Used ordering: 8.43/2.88 Polynomial interpretation [POLO]: 8.43/2.88 8.43/2.88 POL(0_0) = 0 8.43/2.88 POL(M_1) = 1 8.43/2.88 POL(cons_1(x_1, x_2)) = 1 + 2*x_1 8.43/2.88 POL(cons_2(x_1, x_2)) = 2 8.43/2.88 POL(cons_8(x_1, x_2)) = 2 8.43/2.88 POL(garbage_collection_0) = 1 8.43/2.88 POL(h_1(x_1)) = 0 8.43/2.88 POL(tail_0(x_1)) = 2*x_1 8.43/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.43/2.88 8.43/2.88 M_1 -> h_1(cons_1(0_0, tail_0(M_1))) 8.43/2.88 cons_2(x, s) -> garbage_collection_0 8.43/2.88 cons_8(x, s) -> garbage_collection_0 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (24) 8.43/2.88 Obligation: 8.43/2.88 Context-sensitive rewrite system: 8.43/2.88 R is empty. 8.43/2.88 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (25) RisEmptyProof (EQUIVALENT) 8.43/2.88 The CSR R is empty. Hence, termination is trivially proven. 8.43/2.88 ---------------------------------------- 8.43/2.88 8.43/2.88 (26) 8.43/2.88 YES 8.43/2.91 EOF