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