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