/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Quasi decreasingness of the given CTRS could be proven: (0) CTRS (1) CTRSToQTRSProof [SOUND, 0 ms] (2) QTRS (3) AAECC Innermost [EQUIVALENT, 0 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) QReductionProof [EQUIVALENT, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) QReductionProof [EQUIVALENT, 0 ms] (34) QDP (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] (36) YES (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QReductionProof [EQUIVALENT, 0 ms] (41) QDP (42) QDPSizeChangeProof [EQUIVALENT, 0 ms] (43) YES (44) QDP (45) UsableRulesProof [EQUIVALENT, 0 ms] (46) QDP (47) QReductionProof [EQUIVALENT, 0 ms] (48) QDP (49) QDPSizeChangeProof [EQUIVALENT, 0 ms] (50) YES (51) QDP (52) UsableRulesProof [EQUIVALENT, 0 ms] (53) QDP (54) QReductionProof [EQUIVALENT, 0 ms] (55) QDP (56) TransformationProof [EQUIVALENT, 0 ms] (57) QDP (58) TransformationProof [EQUIVALENT, 0 ms] (59) QDP (60) TransformationProof [EQUIVALENT, 0 ms] (61) QDP (62) UsableRulesProof [EQUIVALENT, 0 ms] (63) QDP (64) QReductionProof [EQUIVALENT, 0 ms] (65) QDP (66) TransformationProof [EQUIVALENT, 0 ms] (67) QDP (68) TransformationProof [EQUIVALENT, 0 ms] (69) QDP (70) TransformationProof [EQUIVALENT, 0 ms] (71) QDP (72) UsableRulesProof [EQUIVALENT, 0 ms] (73) QDP (74) QReductionProof [EQUIVALENT, 0 ms] (75) QDP (76) TransformationProof [EQUIVALENT, 0 ms] (77) QDP (78) TransformationProof [EQUIVALENT, 0 ms] (79) QDP (80) DependencyGraphProof [EQUIVALENT, 0 ms] (81) QDP (82) TransformationProof [EQUIVALENT, 0 ms] (83) QDP (84) TransformationProof [EQUIVALENT, 0 ms] (85) QDP (86) TransformationProof [EQUIVALENT, 0 ms] (87) QDP (88) DependencyGraphProof [EQUIVALENT, 0 ms] (89) QDP (90) UsableRulesProof [EQUIVALENT, 0 ms] (91) QDP (92) TransformationProof [EQUIVALENT, 0 ms] (93) QDP (94) UsableRulesProof [EQUIVALENT, 0 ms] (95) QDP (96) QReductionProof [EQUIVALENT, 0 ms] (97) QDP (98) TransformationProof [EQUIVALENT, 0 ms] (99) QDP (100) DependencyGraphProof [EQUIVALENT, 0 ms] (101) QDP (102) TransformationProof [EQUIVALENT, 0 ms] (103) QDP (104) TransformationProof [EQUIVALENT, 0 ms] (105) QDP (106) QDPOrderProof [EQUIVALENT, 25 ms] (107) QDP (108) DependencyGraphProof [EQUIVALENT, 0 ms] (109) TRUE ---------------------------------------- (0) Obligation: Conditional term rewrite system: The TRS R consists of the following rules: fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The conditional TRS C consists of the following conditional rules: process(store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) <= leq(m, length(store)) -> true, empty(fstsplit(m, store)) -> false process(store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) <= leq(m, length(store)) -> false, empty(fstsplit(m, app(map_f(self, nil), store))) -> false ---------------------------------------- (1) CTRSToQTRSProof (SOUND) The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) Q is empty. ---------------------------------------- (3) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The TRS R 2 is process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) The signature Sigma is {process_2, U1_3, U3_3, U2_3} ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) PROCESS(store, m) -> LEQ(m, length(store)) PROCESS(store, m) -> LENGTH(store) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U1^1(false, store, m) -> EMPTY(fstsplit(m, app(map_f(self, nil), store))) U1^1(false, store, m) -> FSTSPLIT(m, app(map_f(self, nil), store)) U1^1(false, store, m) -> APP(map_f(self, nil), store) U1^1(false, store, m) -> MAP_F(self, nil) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) U3^1(false, store, m) -> SNDSPLIT(m, app(map_f(self, nil), store)) U3^1(false, store, m) -> APP(map_f(self, nil), store) U3^1(false, store, m) -> MAP_F(self, nil) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(true, store, m) -> EMPTY(fstsplit(m, store)) U1^1(true, store, m) -> FSTSPLIT(m, store) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) U2^1(false, store, m) -> APP(map_f(self, nil), sndsplit(m, store)) U2^1(false, store, m) -> MAP_F(self, nil) U2^1(false, store, m) -> SNDSPLIT(m, store) FSTSPLIT(s(n), cons(h, t)) -> FSTSPLIT(n, t) SNDSPLIT(s(n), cons(h, t)) -> SNDSPLIT(n, t) LEQ(s(n), s(m)) -> LEQ(n, m) LENGTH(cons(h, t)) -> LENGTH(t) APP(cons(h, t), x) -> APP(t, x) MAP_F(pid, cons(h, t)) -> APP(f(pid, h), map_f(pid, t)) MAP_F(pid, cons(h, t)) -> MAP_F(pid, t) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 15 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: APP(cons(h, t), x) -> APP(t, x) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APP(cons(h, t), x) -> APP(t, x) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: APP(cons(h, t), x) -> APP(t, x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *APP(cons(h, t), x) -> APP(t, x) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MAP_F(pid, cons(h, t)) -> MAP_F(pid, t) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MAP_F(pid, cons(h, t)) -> MAP_F(pid, t) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: MAP_F(pid, cons(h, t)) -> MAP_F(pid, t) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MAP_F(pid, cons(h, t)) -> MAP_F(pid, t) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(h, t)) -> LENGTH(t) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(h, t)) -> LENGTH(t) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTH(cons(h, t)) -> LENGTH(t) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LENGTH(cons(h, t)) -> LENGTH(t) The graph contains the following edges 1 > 1 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: LEQ(s(n), s(m)) -> LEQ(n, m) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: LEQ(s(n), s(m)) -> LEQ(n, m) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: LEQ(s(n), s(m)) -> LEQ(n, m) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LEQ(s(n), s(m)) -> LEQ(n, m) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (36) YES ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: SNDSPLIT(s(n), cons(h, t)) -> SNDSPLIT(n, t) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: SNDSPLIT(s(n), cons(h, t)) -> SNDSPLIT(n, t) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: SNDSPLIT(s(n), cons(h, t)) -> SNDSPLIT(n, t) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *SNDSPLIT(s(n), cons(h, t)) -> SNDSPLIT(n, t) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (43) YES ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: FSTSPLIT(s(n), cons(h, t)) -> FSTSPLIT(n, t) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: FSTSPLIT(s(n), cons(h, t)) -> FSTSPLIT(n, t) R is empty. The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: FSTSPLIT(s(n), cons(h, t)) -> FSTSPLIT(n, t) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *FSTSPLIT(s(n), cons(h, t)) -> FSTSPLIT(n, t) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (50) YES ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) The TRS R consists of the following rules: process(store, m) -> U1(leq(m, length(store)), store, m) U1(false, store, m) -> U3(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3(false, store, m) -> process(sndsplit(m, app(map_f(self, nil), store)), m) U1(true, store, m) -> U2(empty(fstsplit(m, store)), store, m) U2(false, store, m) -> process(app(map_f(self, nil), sndsplit(m, store)), m) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) empty(nil) -> true empty(cons(h, t)) -> false leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) map_f(pid, nil) -> nil map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t)) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) The TRS R consists of the following rules: map_f(pid, nil) -> nil sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. process(x0, x1) U1(false, x0, x1) U3(false, x0, x1) U1(true, x0, x1) U2(false, x0, x1) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) The TRS R consists of the following rules: map_f(pid, nil) -> nil sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(map_f(self, nil), store))), store, m) at position [0,0,1,0] we obtained the following new rules [LPAR04]: (U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m),U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m)) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) The TRS R consists of the following rules: map_f(pid, nil) -> nil sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U3^1(false, store, m) -> PROCESS(sndsplit(m, app(map_f(self, nil), store)), m) at position [0,1,0] we obtained the following new rules [LPAR04]: (U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m),U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m)) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) The TRS R consists of the following rules: map_f(pid, nil) -> nil sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2^1(false, store, m) -> PROCESS(app(map_f(self, nil), sndsplit(m, store)), m) at position [0,0] we obtained the following new rules [LPAR04]: (U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m),U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m)) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) The TRS R consists of the following rules: map_f(pid, nil) -> nil sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x app(cons(h, t), x) -> cons(h, app(t, x)) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) map_f(x0, nil) map_f(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. map_f(x0, nil) map_f(x0, cons(x1, x2)) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1^1(false, store, m) -> U3^1(empty(fstsplit(m, app(nil, store))), store, m) at position [0,0,1] we obtained the following new rules [LPAR04]: (U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m),U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m)) ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U3^1(false, store, m) -> PROCESS(sndsplit(m, app(nil, store)), m) at position [0,1] we obtained the following new rules [LPAR04]: (U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m),U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m)) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2^1(false, store, m) -> PROCESS(app(nil, sndsplit(m, store)), m) at position [0] we obtained the following new rules [LPAR04]: (U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m),U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m)) ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) app(nil, x) -> x fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) app(nil, x0) app(cons(x0, x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. app(nil, x0) app(cons(x0, x1), x2) ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule PROCESS(store, m) -> U1^1(leq(m, length(store)), store, m) at position [0] we obtained the following new rules [LPAR04]: (PROCESS(y0, 0) -> U1^1(true, y0, 0),PROCESS(y0, 0) -> U1^1(true, y0, 0)) (PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1),PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1)) (PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1),PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1)) ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) PROCESS(y0, 0) -> U1^1(true, y0, 0) PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U1^1(true, store, m) -> U2^1(empty(fstsplit(m, store)), store, m) at position [0] we obtained the following new rules [LPAR04]: (U1^1(true, x0, 0) -> U2^1(empty(nil), x0, 0),U1^1(true, x0, 0) -> U2^1(empty(nil), x0, 0)) (U1^1(true, nil, s(x0)) -> U2^1(empty(nil), nil, s(x0)),U1^1(true, nil, s(x0)) -> U2^1(empty(nil), nil, s(x0))) (U1^1(true, cons(x1, x2), s(x0)) -> U2^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)),U1^1(true, cons(x1, x2), s(x0)) -> U2^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0))) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) PROCESS(y0, 0) -> U1^1(true, y0, 0) PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, x0, 0) -> U2^1(empty(nil), x0, 0) U1^1(true, nil, s(x0)) -> U2^1(empty(nil), nil, s(x0)) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1^1(true, cons(x1, x2), s(x0)) -> U2^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) at position [0] we obtained the following new rules [LPAR04]: (U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)),U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0))) ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U3^1(false, store, m) -> PROCESS(sndsplit(m, store), m) at position [0] we obtained the following new rules [LPAR04]: (U3^1(false, x0, 0) -> PROCESS(x0, 0),U3^1(false, x0, 0) -> PROCESS(x0, 0)) (U3^1(false, nil, s(x0)) -> PROCESS(nil, s(x0)),U3^1(false, nil, s(x0)) -> PROCESS(nil, s(x0))) (U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)),U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0))) ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U3^1(false, x0, 0) -> PROCESS(x0, 0) U3^1(false, nil, s(x0)) -> PROCESS(nil, s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U1^1(false, store, m) -> U3^1(empty(fstsplit(m, store)), store, m) at position [0] we obtained the following new rules [LPAR04]: (U1^1(false, x0, 0) -> U3^1(empty(nil), x0, 0),U1^1(false, x0, 0) -> U3^1(empty(nil), x0, 0)) (U1^1(false, nil, s(x0)) -> U3^1(empty(nil), nil, s(x0)),U1^1(false, nil, s(x0)) -> U3^1(empty(nil), nil, s(x0))) (U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)),U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0))) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(nil, y1) -> U1^1(leq(y1, 0), nil, y1) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U3^1(false, x0, 0) -> PROCESS(x0, 0) U3^1(false, nil, s(x0)) -> PROCESS(nil, s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, x0, 0) -> U3^1(empty(nil), x0, 0) U1^1(false, nil, s(x0)) -> U3^1(empty(nil), nil, s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(nil) -> true empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), 0) -> false leq(s(n), s(m)) -> leq(n, m) The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (92) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U1^1(false, cons(x1, x2), s(x0)) -> U3^1(empty(cons(x1, fstsplit(x0, x2))), cons(x1, x2), s(x0)) at position [0] we obtained the following new rules [LPAR04]: (U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)),U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0))) ---------------------------------------- (93) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) fstsplit(0, x) -> nil fstsplit(s(n), nil) -> nil fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t)) empty(cons(h, t)) -> false length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (94) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (95) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. fstsplit(0, x0) fstsplit(s(x0), nil) fstsplit(s(x0), cons(x1, x2)) empty(nil) empty(cons(x0, x1)) ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (98) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U2^1(false, store, m) -> PROCESS(sndsplit(m, store), m) at position [0] we obtained the following new rules [LPAR04]: (U2^1(false, x0, 0) -> PROCESS(x0, 0),U2^1(false, x0, 0) -> PROCESS(x0, 0)) (U2^1(false, nil, s(x0)) -> PROCESS(nil, s(x0)),U2^1(false, nil, s(x0)) -> PROCESS(nil, s(x0))) (U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)),U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0))) ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) U2^1(false, x0, 0) -> PROCESS(x0, 0) U2^1(false, nil, s(x0)) -> PROCESS(nil, s(x0)) U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule PROCESS(cons(x0, x1), y1) -> U1^1(leq(y1, s(length(x1))), cons(x0, x1), y1) we obtained the following new rules [LPAR04]: (PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(s(z2), s(length(x1))), cons(x0, x1), s(z2)),PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(s(z2), s(length(x1))), cons(x0, x1), s(z2))) ---------------------------------------- (103) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(s(z2), s(length(x1))), cons(x0, x1), s(z2)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (104) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(s(z2), s(length(x1))), cons(x0, x1), s(z2)) at position [0] we obtained the following new rules [LPAR04]: (PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(z2, length(x1)), cons(x0, x1), s(z2)),PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(z2, length(x1)), cons(x0, x1), s(z2))) ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(z2, length(x1)), cons(x0, x1), s(z2)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U2^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) U1^1(false, cons(x1, x2), s(x0)) -> U3^1(false, cons(x1, x2), s(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( PROCESS_2(x_1, x_2) ) = max{0, 2x_1 - 2} POL( sndsplit_2(x_1, x_2) ) = x_2 POL( 0 ) = 0 POL( s_1(x_1) ) = max{0, 2x_1 - 2} POL( nil ) = 0 POL( cons_2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( U1^1_3(x_1, ..., x_3) ) = x_2 POL( leq_2(x_1, x_2) ) = 1 POL( length_1(x_1) ) = 0 POL( true ) = 0 POL( false ) = 2 POL( U2^1_3(x_1, ..., x_3) ) = x_2 POL( U3^1_3(x_1, ..., x_3) ) = max{0, x_2 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(true, cons(x1, x2), s(x0)) -> U2^1(false, cons(x1, x2), s(x0)) U3^1(false, cons(x1, x2), s(x0)) -> PROCESS(sndsplit(x0, x2), s(x0)) PROCESS(cons(x0, x1), s(z2)) -> U1^1(leq(z2, length(x1)), cons(x0, x1), s(z2)) The TRS R consists of the following rules: sndsplit(0, x) -> x sndsplit(s(n), nil) -> nil sndsplit(s(n), cons(h, t)) -> sndsplit(n, t) length(nil) -> 0 length(cons(h, t)) -> s(length(t)) leq(0, m) -> true leq(s(n), s(m)) -> leq(n, m) leq(s(n), 0) -> false The set Q consists of the following terms: sndsplit(0, x0) sndsplit(s(x0), nil) sndsplit(s(x0), cons(x1, x2)) leq(0, x0) leq(s(x0), 0) leq(s(x0), s(x1)) length(nil) length(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (108) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (109) TRUE