10.20/4.02 YES 10.20/4.04 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 10.20/4.04 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.20/4.04 10.20/4.04 10.20/4.04 Termination w.r.t. Q of the given QTRS could be proven: 10.20/4.04 10.20/4.04 (0) QTRS 10.20/4.04 (1) QTRSRRRProof [EQUIVALENT, 136 ms] 10.20/4.04 (2) QTRS 10.20/4.04 (3) QTRSRRRProof [EQUIVALENT, 43 ms] 10.20/4.04 (4) QTRS 10.20/4.04 (5) QTRSRRRProof [EQUIVALENT, 46 ms] 10.20/4.04 (6) QTRS 10.20/4.04 (7) DependencyPairsProof [EQUIVALENT, 33 ms] 10.20/4.04 (8) QDP 10.20/4.04 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 10.20/4.04 (10) AND 10.20/4.04 (11) QDP 10.20/4.04 (12) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (13) QDP 10.20/4.04 (14) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (15) QDP 10.20/4.04 (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (17) YES 10.20/4.04 (18) QDP 10.20/4.04 (19) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (20) QDP 10.20/4.04 (21) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (22) QDP 10.20/4.04 (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (24) YES 10.20/4.04 (25) QDP 10.20/4.04 (26) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (27) QDP 10.20/4.04 (28) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (29) QDP 10.20/4.04 (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (31) YES 10.20/4.04 (32) QDP 10.20/4.04 (33) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (34) QDP 10.20/4.04 (35) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (36) QDP 10.20/4.04 (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (38) YES 10.20/4.04 (39) QDP 10.20/4.04 (40) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (41) QDP 10.20/4.04 (42) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (43) QDP 10.20/4.04 (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (45) YES 10.20/4.04 (46) QDP 10.20/4.04 (47) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (48) QDP 10.20/4.04 (49) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (50) QDP 10.20/4.04 (51) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (52) YES 10.20/4.04 (53) QDP 10.20/4.04 (54) MRRProof [EQUIVALENT, 34 ms] 10.20/4.04 (55) QDP 10.20/4.04 (56) MRRProof [EQUIVALENT, 22 ms] 10.20/4.04 (57) QDP 10.20/4.04 (58) MRRProof [EQUIVALENT, 11 ms] 10.20/4.04 (59) QDP 10.20/4.04 (60) QDPOrderProof [EQUIVALENT, 59 ms] 10.20/4.04 (61) QDP 10.20/4.04 (62) DependencyGraphProof [EQUIVALENT, 0 ms] 10.20/4.04 (63) QDP 10.20/4.04 (64) QDPOrderProof [EQUIVALENT, 35 ms] 10.20/4.04 (65) QDP 10.20/4.04 (66) QDPOrderProof [EQUIVALENT, 18 ms] 10.20/4.04 (67) QDP 10.20/4.04 (68) DependencyGraphProof [EQUIVALENT, 0 ms] 10.20/4.04 (69) QDP 10.20/4.04 (70) UsableRulesProof [EQUIVALENT, 0 ms] 10.20/4.04 (71) QDP 10.20/4.04 (72) QReductionProof [EQUIVALENT, 0 ms] 10.20/4.04 (73) QDP 10.20/4.04 (74) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.20/4.04 (75) YES 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (0) 10.20/4.04 Obligation: 10.20/4.04 Q restricted rewrite system: 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(nil)) -> mark(nil) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(nats) -> mark(adx(zeros)) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 active(head(cons(X, L))) -> mark(X) 10.20/4.04 active(tail(cons(X, L))) -> mark(L) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.04 adx(active(x0)) 10.20/4.04 head(mark(x0)) 10.20/4.04 head(active(x0)) 10.20/4.04 tail(mark(x0)) 10.20/4.04 tail(active(x0)) 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (1) QTRSRRRProof (EQUIVALENT) 10.20/4.04 Used ordering: 10.20/4.04 Polynomial interpretation [POLO]: 10.20/4.04 10.20/4.04 POL(0) = 0 10.20/4.04 POL(active(x_1)) = x_1 10.20/4.04 POL(adx(x_1)) = 2*x_1 10.20/4.04 POL(cons(x_1, x_2)) = 2*x_1 + x_2 10.20/4.04 POL(head(x_1)) = x_1 10.20/4.04 POL(incr(x_1)) = x_1 10.20/4.04 POL(mark(x_1)) = x_1 10.20/4.04 POL(nats) = 0 10.20/4.04 POL(nil) = 2 10.20/4.04 POL(s(x_1)) = x_1 10.20/4.04 POL(tail(x_1)) = x_1 10.20/4.04 POL(zeros) = 0 10.20/4.04 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.20/4.04 10.20/4.04 active(adx(nil)) -> mark(nil) 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (2) 10.20/4.04 Obligation: 10.20/4.04 Q restricted rewrite system: 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(nats) -> mark(adx(zeros)) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 active(head(cons(X, L))) -> mark(X) 10.20/4.04 active(tail(cons(X, L))) -> mark(L) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.04 adx(active(x0)) 10.20/4.04 head(mark(x0)) 10.20/4.04 head(active(x0)) 10.20/4.04 tail(mark(x0)) 10.20/4.04 tail(active(x0)) 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (3) QTRSRRRProof (EQUIVALENT) 10.20/4.04 Used ordering: 10.20/4.04 Polynomial interpretation [POLO]: 10.20/4.04 10.20/4.04 POL(0) = 0 10.20/4.04 POL(active(x_1)) = x_1 10.20/4.04 POL(adx(x_1)) = x_1 10.20/4.04 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.20/4.04 POL(head(x_1)) = 1 + x_1 10.20/4.04 POL(incr(x_1)) = x_1 10.20/4.04 POL(mark(x_1)) = x_1 10.20/4.04 POL(nats) = 0 10.20/4.04 POL(nil) = 0 10.20/4.04 POL(s(x_1)) = x_1 10.20/4.04 POL(tail(x_1)) = 1 + 2*x_1 10.20/4.04 POL(zeros) = 0 10.20/4.04 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.20/4.04 10.20/4.04 active(head(cons(X, L))) -> mark(X) 10.20/4.04 active(tail(cons(X, L))) -> mark(L) 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (4) 10.20/4.04 Obligation: 10.20/4.04 Q restricted rewrite system: 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(nats) -> mark(adx(zeros)) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.04 adx(active(x0)) 10.20/4.04 head(mark(x0)) 10.20/4.04 head(active(x0)) 10.20/4.04 tail(mark(x0)) 10.20/4.04 tail(active(x0)) 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (5) QTRSRRRProof (EQUIVALENT) 10.20/4.04 Used ordering: 10.20/4.04 Polynomial interpretation [POLO]: 10.20/4.04 10.20/4.04 POL(0) = 0 10.20/4.04 POL(active(x_1)) = x_1 10.20/4.04 POL(adx(x_1)) = 2*x_1 10.20/4.04 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.20/4.04 POL(head(x_1)) = x_1 10.20/4.04 POL(incr(x_1)) = x_1 10.20/4.04 POL(mark(x_1)) = x_1 10.20/4.04 POL(nats) = 2 10.20/4.04 POL(nil) = 0 10.20/4.04 POL(s(x_1)) = x_1 10.20/4.04 POL(tail(x_1)) = x_1 10.20/4.04 POL(zeros) = 0 10.20/4.04 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.20/4.04 10.20/4.04 active(nats) -> mark(adx(zeros)) 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (6) 10.20/4.04 Obligation: 10.20/4.04 Q restricted rewrite system: 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.04 adx(active(x0)) 10.20/4.04 head(mark(x0)) 10.20/4.04 head(active(x0)) 10.20/4.04 tail(mark(x0)) 10.20/4.04 tail(active(x0)) 10.20/4.04 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (7) DependencyPairsProof (EQUIVALENT) 10.20/4.04 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (8) 10.20/4.04 Obligation: 10.20/4.04 Q DP problem: 10.20/4.04 The TRS P consists of the following rules: 10.20/4.04 10.20/4.04 ACTIVE(incr(nil)) -> MARK(nil) 10.20/4.04 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.04 ACTIVE(incr(cons(X, L))) -> CONS(s(X), incr(L)) 10.20/4.04 ACTIVE(incr(cons(X, L))) -> S(X) 10.20/4.04 ACTIVE(incr(cons(X, L))) -> INCR(L) 10.20/4.04 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.04 ACTIVE(adx(cons(X, L))) -> INCR(cons(X, adx(L))) 10.20/4.04 ACTIVE(adx(cons(X, L))) -> CONS(X, adx(L)) 10.20/4.04 ACTIVE(adx(cons(X, L))) -> ADX(L) 10.20/4.04 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.04 ACTIVE(zeros) -> CONS(0, zeros) 10.20/4.04 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.04 MARK(incr(X)) -> INCR(mark(X)) 10.20/4.04 MARK(incr(X)) -> MARK(X) 10.20/4.04 MARK(nil) -> ACTIVE(nil) 10.20/4.04 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.04 MARK(cons(X1, X2)) -> CONS(mark(X1), X2) 10.20/4.04 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.04 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.04 MARK(s(X)) -> S(mark(X)) 10.20/4.04 MARK(s(X)) -> MARK(X) 10.20/4.04 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.04 MARK(adx(X)) -> ADX(mark(X)) 10.20/4.04 MARK(adx(X)) -> MARK(X) 10.20/4.04 MARK(nats) -> ACTIVE(nats) 10.20/4.04 MARK(zeros) -> ACTIVE(zeros) 10.20/4.04 MARK(0) -> ACTIVE(0) 10.20/4.04 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.04 MARK(head(X)) -> HEAD(mark(X)) 10.20/4.04 MARK(head(X)) -> MARK(X) 10.20/4.04 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.04 MARK(tail(X)) -> TAIL(mark(X)) 10.20/4.04 MARK(tail(X)) -> MARK(X) 10.20/4.04 INCR(mark(X)) -> INCR(X) 10.20/4.04 INCR(active(X)) -> INCR(X) 10.20/4.04 CONS(mark(X1), X2) -> CONS(X1, X2) 10.20/4.04 CONS(X1, mark(X2)) -> CONS(X1, X2) 10.20/4.04 CONS(active(X1), X2) -> CONS(X1, X2) 10.20/4.04 CONS(X1, active(X2)) -> CONS(X1, X2) 10.20/4.04 S(mark(X)) -> S(X) 10.20/4.04 S(active(X)) -> S(X) 10.20/4.04 ADX(mark(X)) -> ADX(X) 10.20/4.04 ADX(active(X)) -> ADX(X) 10.20/4.04 HEAD(mark(X)) -> HEAD(X) 10.20/4.04 HEAD(active(X)) -> HEAD(X) 10.20/4.04 TAIL(mark(X)) -> TAIL(X) 10.20/4.04 TAIL(active(X)) -> TAIL(X) 10.20/4.04 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.04 adx(active(x0)) 10.20/4.04 head(mark(x0)) 10.20/4.04 head(active(x0)) 10.20/4.04 tail(mark(x0)) 10.20/4.04 tail(active(x0)) 10.20/4.04 10.20/4.04 We have to consider all minimal (P,Q,R)-chains. 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (9) DependencyGraphProof (EQUIVALENT) 10.20/4.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 17 less nodes. 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (10) 10.20/4.04 Complex Obligation (AND) 10.20/4.04 10.20/4.04 ---------------------------------------- 10.20/4.04 10.20/4.04 (11) 10.20/4.04 Obligation: 10.20/4.04 Q DP problem: 10.20/4.04 The TRS P consists of the following rules: 10.20/4.04 10.20/4.04 TAIL(active(X)) -> TAIL(X) 10.20/4.04 TAIL(mark(X)) -> TAIL(X) 10.20/4.04 10.20/4.04 The TRS R consists of the following rules: 10.20/4.04 10.20/4.04 active(incr(nil)) -> mark(nil) 10.20/4.04 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.04 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.04 active(zeros) -> mark(cons(0, zeros)) 10.20/4.04 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.04 mark(nil) -> active(nil) 10.20/4.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.04 mark(s(X)) -> active(s(mark(X))) 10.20/4.04 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.04 mark(nats) -> active(nats) 10.20/4.04 mark(zeros) -> active(zeros) 10.20/4.04 mark(0) -> active(0) 10.20/4.04 mark(head(X)) -> active(head(mark(X))) 10.20/4.04 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.04 incr(mark(X)) -> incr(X) 10.20/4.04 incr(active(X)) -> incr(X) 10.20/4.04 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.04 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.04 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.04 s(mark(X)) -> s(X) 10.20/4.04 s(active(X)) -> s(X) 10.20/4.04 adx(mark(X)) -> adx(X) 10.20/4.04 adx(active(X)) -> adx(X) 10.20/4.04 head(mark(X)) -> head(X) 10.20/4.04 head(active(X)) -> head(X) 10.20/4.04 tail(mark(X)) -> tail(X) 10.20/4.04 tail(active(X)) -> tail(X) 10.20/4.04 10.20/4.04 The set Q consists of the following terms: 10.20/4.04 10.20/4.04 active(incr(nil)) 10.20/4.04 active(incr(cons(x0, x1))) 10.20/4.04 active(adx(nil)) 10.20/4.04 active(adx(cons(x0, x1))) 10.20/4.04 active(nats) 10.20/4.04 active(zeros) 10.20/4.04 active(head(cons(x0, x1))) 10.20/4.04 active(tail(cons(x0, x1))) 10.20/4.04 mark(incr(x0)) 10.20/4.04 mark(nil) 10.20/4.04 mark(cons(x0, x1)) 10.20/4.04 mark(s(x0)) 10.20/4.04 mark(adx(x0)) 10.20/4.04 mark(nats) 10.20/4.04 mark(zeros) 10.20/4.04 mark(0) 10.20/4.04 mark(head(x0)) 10.20/4.04 mark(tail(x0)) 10.20/4.04 incr(mark(x0)) 10.20/4.04 incr(active(x0)) 10.20/4.04 cons(mark(x0), x1) 10.20/4.04 cons(x0, mark(x1)) 10.20/4.04 cons(active(x0), x1) 10.20/4.04 cons(x0, active(x1)) 10.20/4.04 s(mark(x0)) 10.20/4.04 s(active(x0)) 10.20/4.04 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (12) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (13) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 TAIL(active(X)) -> TAIL(X) 10.20/4.05 TAIL(mark(X)) -> TAIL(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (14) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (15) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 TAIL(active(X)) -> TAIL(X) 10.20/4.05 TAIL(mark(X)) -> TAIL(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (16) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *TAIL(active(X)) -> TAIL(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 *TAIL(mark(X)) -> TAIL(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (17) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (18) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 HEAD(active(X)) -> HEAD(X) 10.20/4.05 HEAD(mark(X)) -> HEAD(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (19) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (20) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 HEAD(active(X)) -> HEAD(X) 10.20/4.05 HEAD(mark(X)) -> HEAD(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (21) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (22) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 HEAD(active(X)) -> HEAD(X) 10.20/4.05 HEAD(mark(X)) -> HEAD(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (23) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *HEAD(active(X)) -> HEAD(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 *HEAD(mark(X)) -> HEAD(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (24) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (25) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ADX(active(X)) -> ADX(X) 10.20/4.05 ADX(mark(X)) -> ADX(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (26) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (27) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ADX(active(X)) -> ADX(X) 10.20/4.05 ADX(mark(X)) -> ADX(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (28) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (29) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ADX(active(X)) -> ADX(X) 10.20/4.05 ADX(mark(X)) -> ADX(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (30) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *ADX(active(X)) -> ADX(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 *ADX(mark(X)) -> ADX(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (31) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (32) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 S(active(X)) -> S(X) 10.20/4.05 S(mark(X)) -> S(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (33) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (34) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 S(active(X)) -> S(X) 10.20/4.05 S(mark(X)) -> S(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (35) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (36) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 S(active(X)) -> S(X) 10.20/4.05 S(mark(X)) -> S(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (37) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *S(active(X)) -> S(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 *S(mark(X)) -> S(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (38) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (39) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 CONS(X1, mark(X2)) -> CONS(X1, X2) 10.20/4.05 CONS(mark(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(active(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(X1, active(X2)) -> CONS(X1, X2) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (40) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (41) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 CONS(X1, mark(X2)) -> CONS(X1, X2) 10.20/4.05 CONS(mark(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(active(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(X1, active(X2)) -> CONS(X1, X2) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (42) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (43) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 CONS(X1, mark(X2)) -> CONS(X1, X2) 10.20/4.05 CONS(mark(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(active(X1), X2) -> CONS(X1, X2) 10.20/4.05 CONS(X1, active(X2)) -> CONS(X1, X2) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (44) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *CONS(X1, mark(X2)) -> CONS(X1, X2) 10.20/4.05 The graph contains the following edges 1 >= 1, 2 > 2 10.20/4.05 10.20/4.05 10.20/4.05 *CONS(mark(X1), X2) -> CONS(X1, X2) 10.20/4.05 The graph contains the following edges 1 > 1, 2 >= 2 10.20/4.05 10.20/4.05 10.20/4.05 *CONS(active(X1), X2) -> CONS(X1, X2) 10.20/4.05 The graph contains the following edges 1 > 1, 2 >= 2 10.20/4.05 10.20/4.05 10.20/4.05 *CONS(X1, active(X2)) -> CONS(X1, X2) 10.20/4.05 The graph contains the following edges 1 >= 1, 2 > 2 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (45) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (46) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 INCR(active(X)) -> INCR(X) 10.20/4.05 INCR(mark(X)) -> INCR(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (47) UsableRulesProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (48) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 INCR(active(X)) -> INCR(X) 10.20/4.05 INCR(mark(X)) -> INCR(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (49) QReductionProof (EQUIVALENT) 10.20/4.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.05 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (50) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 INCR(active(X)) -> INCR(X) 10.20/4.05 INCR(mark(X)) -> INCR(X) 10.20/4.05 10.20/4.05 R is empty. 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (51) QDPSizeChangeProof (EQUIVALENT) 10.20/4.05 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. 10.20/4.05 10.20/4.05 From the DPs we obtained the following set of size-change graphs: 10.20/4.05 *INCR(active(X)) -> INCR(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 *INCR(mark(X)) -> INCR(X) 10.20/4.05 The graph contains the following edges 1 > 1 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (52) 10.20/4.05 YES 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (53) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(adx(X)) -> MARK(X) 10.20/4.05 MARK(zeros) -> ACTIVE(zeros) 10.20/4.05 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(head(X)) -> MARK(X) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 MARK(tail(X)) -> MARK(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (54) MRRProof (EQUIVALENT) 10.20/4.05 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 10.20/4.05 10.20/4.05 Strictly oriented dependency pairs: 10.20/4.05 10.20/4.05 MARK(head(X)) -> MARK(X) 10.20/4.05 10.20/4.05 10.20/4.05 Used ordering: Polynomial interpretation [POLO]: 10.20/4.05 10.20/4.05 POL(0) = 0 10.20/4.05 POL(ACTIVE(x_1)) = 2*x_1 10.20/4.05 POL(MARK(x_1)) = 2*x_1 10.20/4.05 POL(active(x_1)) = x_1 10.20/4.05 POL(adx(x_1)) = 2*x_1 10.20/4.05 POL(cons(x_1, x_2)) = x_1 + 2*x_2 10.20/4.05 POL(head(x_1)) = 2 + x_1 10.20/4.05 POL(incr(x_1)) = x_1 10.20/4.05 POL(mark(x_1)) = x_1 10.20/4.05 POL(nats) = 0 10.20/4.05 POL(nil) = 0 10.20/4.05 POL(s(x_1)) = x_1 10.20/4.05 POL(tail(x_1)) = 2*x_1 10.20/4.05 POL(zeros) = 0 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (55) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(adx(X)) -> MARK(X) 10.20/4.05 MARK(zeros) -> ACTIVE(zeros) 10.20/4.05 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 MARK(tail(X)) -> MARK(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (56) MRRProof (EQUIVALENT) 10.20/4.05 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 10.20/4.05 10.20/4.05 Strictly oriented dependency pairs: 10.20/4.05 10.20/4.05 MARK(adx(X)) -> MARK(X) 10.20/4.05 10.20/4.05 10.20/4.05 Used ordering: Polynomial interpretation [POLO]: 10.20/4.05 10.20/4.05 POL(0) = 0 10.20/4.05 POL(ACTIVE(x_1)) = 2*x_1 10.20/4.05 POL(MARK(x_1)) = 2*x_1 10.20/4.05 POL(active(x_1)) = x_1 10.20/4.05 POL(adx(x_1)) = 2 + x_1 10.20/4.05 POL(cons(x_1, x_2)) = 2*x_1 + x_2 10.20/4.05 POL(head(x_1)) = 2*x_1 10.20/4.05 POL(incr(x_1)) = x_1 10.20/4.05 POL(mark(x_1)) = x_1 10.20/4.05 POL(nats) = 0 10.20/4.05 POL(nil) = 0 10.20/4.05 POL(s(x_1)) = x_1 10.20/4.05 POL(tail(x_1)) = 2*x_1 10.20/4.05 POL(zeros) = 0 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (57) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(zeros) -> ACTIVE(zeros) 10.20/4.05 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 MARK(tail(X)) -> MARK(X) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (58) MRRProof (EQUIVALENT) 10.20/4.05 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 10.20/4.05 10.20/4.05 Strictly oriented dependency pairs: 10.20/4.05 10.20/4.05 MARK(tail(X)) -> MARK(X) 10.20/4.05 10.20/4.05 10.20/4.05 Used ordering: Polynomial interpretation [POLO]: 10.20/4.05 10.20/4.05 POL(0) = 0 10.20/4.05 POL(ACTIVE(x_1)) = 2*x_1 10.20/4.05 POL(MARK(x_1)) = 2*x_1 10.20/4.05 POL(active(x_1)) = x_1 10.20/4.05 POL(adx(x_1)) = x_1 10.20/4.05 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.20/4.05 POL(head(x_1)) = x_1 10.20/4.05 POL(incr(x_1)) = x_1 10.20/4.05 POL(mark(x_1)) = x_1 10.20/4.05 POL(nats) = 0 10.20/4.05 POL(nil) = 0 10.20/4.05 POL(s(x_1)) = x_1 10.20/4.05 POL(tail(x_1)) = 2 + 2*x_1 10.20/4.05 POL(zeros) = 0 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (59) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(zeros) -> ACTIVE(zeros) 10.20/4.05 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (60) QDPOrderProof (EQUIVALENT) 10.20/4.05 We use the reduction pair processor [LPAR04,JAR06]. 10.20/4.05 10.20/4.05 10.20/4.05 The following pairs can be oriented strictly and are deleted. 10.20/4.05 10.20/4.05 ACTIVE(zeros) -> MARK(cons(0, zeros)) 10.20/4.05 The remaining pairs can at least be oriented weakly. 10.20/4.05 Used ordering: Combined order from the following AFS and order. 10.20/4.05 ACTIVE(x1) = x1 10.20/4.05 10.20/4.05 incr(x1) = x1 10.20/4.05 10.20/4.05 cons(x1, x2) = x1 10.20/4.05 10.20/4.05 MARK(x1) = x1 10.20/4.05 10.20/4.05 s(x1) = x1 10.20/4.05 10.20/4.05 mark(x1) = x1 10.20/4.05 10.20/4.05 adx(x1) = x1 10.20/4.05 10.20/4.05 zeros = zeros 10.20/4.05 10.20/4.05 0 = 0 10.20/4.05 10.20/4.05 head(x1) = head 10.20/4.05 10.20/4.05 tail(x1) = tail 10.20/4.05 10.20/4.05 active(x1) = x1 10.20/4.05 10.20/4.05 nil = nil 10.20/4.05 10.20/4.05 nats = nats 10.20/4.05 10.20/4.05 10.20/4.05 Knuth-Bendix order [KBO] with precedence:trivial 10.20/4.05 10.20/4.05 and weight map: 10.20/4.05 10.20/4.05 nats=1 10.20/4.05 tail=2 10.20/4.05 0=2 10.20/4.05 head=2 10.20/4.05 zeros=3 10.20/4.05 nil=2 10.20/4.05 10.20/4.05 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 10.20/4.05 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (61) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(zeros) -> ACTIVE(zeros) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (62) DependencyGraphProof (EQUIVALENT) 10.20/4.05 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (63) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (64) QDPOrderProof (EQUIVALENT) 10.20/4.05 We use the reduction pair processor [LPAR04,JAR06]. 10.20/4.05 10.20/4.05 10.20/4.05 The following pairs can be oriented strictly and are deleted. 10.20/4.05 10.20/4.05 ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 10.20/4.05 The remaining pairs can at least be oriented weakly. 10.20/4.05 Used ordering: Combined order from the following AFS and order. 10.20/4.05 MARK(x1) = x1 10.20/4.05 10.20/4.05 cons(x1, x2) = x1 10.20/4.05 10.20/4.05 ACTIVE(x1) = x1 10.20/4.05 10.20/4.05 mark(x1) = x1 10.20/4.05 10.20/4.05 incr(x1) = x1 10.20/4.05 10.20/4.05 s(x1) = x1 10.20/4.05 10.20/4.05 adx(x1) = adx(x1) 10.20/4.05 10.20/4.05 head(x1) = head 10.20/4.05 10.20/4.05 tail(x1) = tail 10.20/4.05 10.20/4.05 active(x1) = x1 10.20/4.05 10.20/4.05 zeros = zeros 10.20/4.05 10.20/4.05 0 = 0 10.20/4.05 10.20/4.05 nil = nil 10.20/4.05 10.20/4.05 nats = nats 10.20/4.05 10.20/4.05 10.20/4.05 Knuth-Bendix order [KBO] with precedence:trivial 10.20/4.05 10.20/4.05 and weight map: 10.20/4.05 10.20/4.05 nats=1 10.20/4.05 tail=2 10.20/4.05 zeros=3 10.20/4.05 0=2 10.20/4.05 head=2 10.20/4.05 adx_1=1 10.20/4.05 nil=2 10.20/4.05 10.20/4.05 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 10.20/4.05 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 10.20/4.05 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (65) 10.20/4.05 Obligation: 10.20/4.05 Q DP problem: 10.20/4.05 The TRS P consists of the following rules: 10.20/4.05 10.20/4.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.05 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.05 MARK(s(X)) -> MARK(X) 10.20/4.05 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.05 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.05 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.05 10.20/4.05 The TRS R consists of the following rules: 10.20/4.05 10.20/4.05 active(incr(nil)) -> mark(nil) 10.20/4.05 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.05 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.05 active(zeros) -> mark(cons(0, zeros)) 10.20/4.05 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.05 mark(nil) -> active(nil) 10.20/4.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.05 mark(s(X)) -> active(s(mark(X))) 10.20/4.05 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.05 mark(nats) -> active(nats) 10.20/4.05 mark(zeros) -> active(zeros) 10.20/4.05 mark(0) -> active(0) 10.20/4.05 mark(head(X)) -> active(head(mark(X))) 10.20/4.05 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.05 incr(mark(X)) -> incr(X) 10.20/4.05 incr(active(X)) -> incr(X) 10.20/4.05 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.05 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.05 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.05 s(mark(X)) -> s(X) 10.20/4.05 s(active(X)) -> s(X) 10.20/4.05 adx(mark(X)) -> adx(X) 10.20/4.05 adx(active(X)) -> adx(X) 10.20/4.05 head(mark(X)) -> head(X) 10.20/4.05 head(active(X)) -> head(X) 10.20/4.05 tail(mark(X)) -> tail(X) 10.20/4.05 tail(active(X)) -> tail(X) 10.20/4.05 10.20/4.05 The set Q consists of the following terms: 10.20/4.05 10.20/4.05 active(incr(nil)) 10.20/4.05 active(incr(cons(x0, x1))) 10.20/4.05 active(adx(nil)) 10.20/4.05 active(adx(cons(x0, x1))) 10.20/4.05 active(nats) 10.20/4.05 active(zeros) 10.20/4.05 active(head(cons(x0, x1))) 10.20/4.05 active(tail(cons(x0, x1))) 10.20/4.05 mark(incr(x0)) 10.20/4.05 mark(nil) 10.20/4.05 mark(cons(x0, x1)) 10.20/4.05 mark(s(x0)) 10.20/4.05 mark(adx(x0)) 10.20/4.05 mark(nats) 10.20/4.05 mark(zeros) 10.20/4.05 mark(0) 10.20/4.05 mark(head(x0)) 10.20/4.05 mark(tail(x0)) 10.20/4.05 incr(mark(x0)) 10.20/4.05 incr(active(x0)) 10.20/4.05 cons(mark(x0), x1) 10.20/4.05 cons(x0, mark(x1)) 10.20/4.05 cons(active(x0), x1) 10.20/4.05 cons(x0, active(x1)) 10.20/4.05 s(mark(x0)) 10.20/4.05 s(active(x0)) 10.20/4.05 adx(mark(x0)) 10.20/4.05 adx(active(x0)) 10.20/4.05 head(mark(x0)) 10.20/4.05 head(active(x0)) 10.20/4.05 tail(mark(x0)) 10.20/4.05 tail(active(x0)) 10.20/4.05 10.20/4.05 We have to consider all minimal (P,Q,R)-chains. 10.20/4.05 ---------------------------------------- 10.20/4.05 10.20/4.05 (66) QDPOrderProof (EQUIVALENT) 10.20/4.05 We use the reduction pair processor [LPAR04,JAR06]. 10.20/4.05 10.20/4.05 10.20/4.05 The following pairs can be oriented strictly and are deleted. 10.20/4.05 10.20/4.05 ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) 10.20/4.05 MARK(incr(X)) -> MARK(X) 10.20/4.05 The remaining pairs can at least be oriented weakly. 10.20/4.05 Used ordering: Combined order from the following AFS and order. 10.20/4.05 MARK(x1) = x1 10.20/4.05 10.20/4.05 cons(x1, x2) = x1 10.20/4.05 10.20/4.05 ACTIVE(x1) = x1 10.20/4.05 10.20/4.05 mark(x1) = x1 10.20/4.05 10.20/4.05 incr(x1) = incr(x1) 10.20/4.05 10.20/4.05 s(x1) = x1 10.20/4.05 10.20/4.05 adx(x1) = adx(x1) 10.20/4.05 10.20/4.05 head(x1) = head 10.20/4.05 10.20/4.05 tail(x1) = tail 10.20/4.05 10.20/4.05 active(x1) = x1 10.20/4.05 10.20/4.05 zeros = zeros 10.20/4.06 10.20/4.06 0 = 0 10.20/4.06 10.20/4.06 nil = nil 10.20/4.06 10.20/4.06 nats = nats 10.20/4.06 10.20/4.06 10.20/4.06 Knuth-Bendix order [KBO] with precedence:trivial 10.20/4.06 10.20/4.06 and weight map: 10.20/4.06 10.20/4.06 nats=1 10.20/4.06 tail=2 10.20/4.06 zeros=3 10.20/4.06 0=2 10.20/4.06 head=2 10.20/4.06 incr_1=1 10.20/4.06 adx_1=2 10.20/4.06 nil=2 10.20/4.06 10.20/4.06 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 10.20/4.06 10.20/4.06 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.06 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.06 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.06 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.06 active(zeros) -> mark(cons(0, zeros)) 10.20/4.06 mark(nil) -> active(nil) 10.20/4.06 mark(s(X)) -> active(s(mark(X))) 10.20/4.06 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.06 mark(nats) -> active(nats) 10.20/4.06 mark(zeros) -> active(zeros) 10.20/4.06 mark(0) -> active(0) 10.20/4.06 mark(head(X)) -> active(head(mark(X))) 10.20/4.06 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.06 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.06 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.06 incr(active(X)) -> incr(X) 10.20/4.06 incr(mark(X)) -> incr(X) 10.20/4.06 s(active(X)) -> s(X) 10.20/4.06 s(mark(X)) -> s(X) 10.20/4.06 adx(active(X)) -> adx(X) 10.20/4.06 adx(mark(X)) -> adx(X) 10.20/4.06 head(active(X)) -> head(X) 10.20/4.06 head(mark(X)) -> head(X) 10.20/4.06 tail(active(X)) -> tail(X) 10.20/4.06 tail(mark(X)) -> tail(X) 10.20/4.06 active(incr(nil)) -> mark(nil) 10.20/4.06 10.20/4.06 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (67) 10.20/4.06 Obligation: 10.20/4.06 Q DP problem: 10.20/4.06 The TRS P consists of the following rules: 10.20/4.06 10.20/4.06 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 10.20/4.06 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.06 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 10.20/4.06 MARK(s(X)) -> ACTIVE(s(mark(X))) 10.20/4.06 MARK(s(X)) -> MARK(X) 10.20/4.06 MARK(adx(X)) -> ACTIVE(adx(mark(X))) 10.20/4.06 MARK(head(X)) -> ACTIVE(head(mark(X))) 10.20/4.06 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 10.20/4.06 10.20/4.06 The TRS R consists of the following rules: 10.20/4.06 10.20/4.06 active(incr(nil)) -> mark(nil) 10.20/4.06 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.06 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.06 active(zeros) -> mark(cons(0, zeros)) 10.20/4.06 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.06 mark(nil) -> active(nil) 10.20/4.06 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.06 mark(s(X)) -> active(s(mark(X))) 10.20/4.06 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.06 mark(nats) -> active(nats) 10.20/4.06 mark(zeros) -> active(zeros) 10.20/4.06 mark(0) -> active(0) 10.20/4.06 mark(head(X)) -> active(head(mark(X))) 10.20/4.06 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.06 incr(mark(X)) -> incr(X) 10.20/4.06 incr(active(X)) -> incr(X) 10.20/4.06 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.06 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.06 s(mark(X)) -> s(X) 10.20/4.06 s(active(X)) -> s(X) 10.20/4.06 adx(mark(X)) -> adx(X) 10.20/4.06 adx(active(X)) -> adx(X) 10.20/4.06 head(mark(X)) -> head(X) 10.20/4.06 head(active(X)) -> head(X) 10.20/4.06 tail(mark(X)) -> tail(X) 10.20/4.06 tail(active(X)) -> tail(X) 10.20/4.06 10.20/4.06 The set Q consists of the following terms: 10.20/4.06 10.20/4.06 active(incr(nil)) 10.20/4.06 active(incr(cons(x0, x1))) 10.20/4.06 active(adx(nil)) 10.20/4.06 active(adx(cons(x0, x1))) 10.20/4.06 active(nats) 10.20/4.06 active(zeros) 10.20/4.06 active(head(cons(x0, x1))) 10.20/4.06 active(tail(cons(x0, x1))) 10.20/4.06 mark(incr(x0)) 10.20/4.06 mark(nil) 10.20/4.06 mark(cons(x0, x1)) 10.20/4.06 mark(s(x0)) 10.20/4.06 mark(adx(x0)) 10.20/4.06 mark(nats) 10.20/4.06 mark(zeros) 10.20/4.06 mark(0) 10.20/4.06 mark(head(x0)) 10.20/4.06 mark(tail(x0)) 10.20/4.06 incr(mark(x0)) 10.20/4.06 incr(active(x0)) 10.20/4.06 cons(mark(x0), x1) 10.20/4.06 cons(x0, mark(x1)) 10.20/4.06 cons(active(x0), x1) 10.20/4.06 cons(x0, active(x1)) 10.20/4.06 s(mark(x0)) 10.20/4.06 s(active(x0)) 10.20/4.06 adx(mark(x0)) 10.20/4.06 adx(active(x0)) 10.20/4.06 head(mark(x0)) 10.20/4.06 head(active(x0)) 10.20/4.06 tail(mark(x0)) 10.20/4.06 tail(active(x0)) 10.20/4.06 10.20/4.06 We have to consider all minimal (P,Q,R)-chains. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (68) DependencyGraphProof (EQUIVALENT) 10.20/4.06 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (69) 10.20/4.06 Obligation: 10.20/4.06 Q DP problem: 10.20/4.06 The TRS P consists of the following rules: 10.20/4.06 10.20/4.06 MARK(s(X)) -> MARK(X) 10.20/4.06 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.06 10.20/4.06 The TRS R consists of the following rules: 10.20/4.06 10.20/4.06 active(incr(nil)) -> mark(nil) 10.20/4.06 active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) 10.20/4.06 active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) 10.20/4.06 active(zeros) -> mark(cons(0, zeros)) 10.20/4.06 mark(incr(X)) -> active(incr(mark(X))) 10.20/4.06 mark(nil) -> active(nil) 10.20/4.06 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 10.20/4.06 mark(s(X)) -> active(s(mark(X))) 10.20/4.06 mark(adx(X)) -> active(adx(mark(X))) 10.20/4.06 mark(nats) -> active(nats) 10.20/4.06 mark(zeros) -> active(zeros) 10.20/4.06 mark(0) -> active(0) 10.20/4.06 mark(head(X)) -> active(head(mark(X))) 10.20/4.06 mark(tail(X)) -> active(tail(mark(X))) 10.20/4.06 incr(mark(X)) -> incr(X) 10.20/4.06 incr(active(X)) -> incr(X) 10.20/4.06 cons(mark(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(X1, mark(X2)) -> cons(X1, X2) 10.20/4.06 cons(active(X1), X2) -> cons(X1, X2) 10.20/4.06 cons(X1, active(X2)) -> cons(X1, X2) 10.20/4.06 s(mark(X)) -> s(X) 10.20/4.06 s(active(X)) -> s(X) 10.20/4.06 adx(mark(X)) -> adx(X) 10.20/4.06 adx(active(X)) -> adx(X) 10.20/4.06 head(mark(X)) -> head(X) 10.20/4.06 head(active(X)) -> head(X) 10.20/4.06 tail(mark(X)) -> tail(X) 10.20/4.06 tail(active(X)) -> tail(X) 10.20/4.06 10.20/4.06 The set Q consists of the following terms: 10.20/4.06 10.20/4.06 active(incr(nil)) 10.20/4.06 active(incr(cons(x0, x1))) 10.20/4.06 active(adx(nil)) 10.20/4.06 active(adx(cons(x0, x1))) 10.20/4.06 active(nats) 10.20/4.06 active(zeros) 10.20/4.06 active(head(cons(x0, x1))) 10.20/4.06 active(tail(cons(x0, x1))) 10.20/4.06 mark(incr(x0)) 10.20/4.06 mark(nil) 10.20/4.06 mark(cons(x0, x1)) 10.20/4.06 mark(s(x0)) 10.20/4.06 mark(adx(x0)) 10.20/4.06 mark(nats) 10.20/4.06 mark(zeros) 10.20/4.06 mark(0) 10.20/4.06 mark(head(x0)) 10.20/4.06 mark(tail(x0)) 10.20/4.06 incr(mark(x0)) 10.20/4.06 incr(active(x0)) 10.20/4.06 cons(mark(x0), x1) 10.20/4.06 cons(x0, mark(x1)) 10.20/4.06 cons(active(x0), x1) 10.20/4.06 cons(x0, active(x1)) 10.20/4.06 s(mark(x0)) 10.20/4.06 s(active(x0)) 10.20/4.06 adx(mark(x0)) 10.20/4.06 adx(active(x0)) 10.20/4.06 head(mark(x0)) 10.20/4.06 head(active(x0)) 10.20/4.06 tail(mark(x0)) 10.20/4.06 tail(active(x0)) 10.20/4.06 10.20/4.06 We have to consider all minimal (P,Q,R)-chains. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (70) UsableRulesProof (EQUIVALENT) 10.20/4.06 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. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (71) 10.20/4.06 Obligation: 10.20/4.06 Q DP problem: 10.20/4.06 The TRS P consists of the following rules: 10.20/4.06 10.20/4.06 MARK(s(X)) -> MARK(X) 10.20/4.06 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.06 10.20/4.06 R is empty. 10.20/4.06 The set Q consists of the following terms: 10.20/4.06 10.20/4.06 active(incr(nil)) 10.20/4.06 active(incr(cons(x0, x1))) 10.20/4.06 active(adx(nil)) 10.20/4.06 active(adx(cons(x0, x1))) 10.20/4.06 active(nats) 10.20/4.06 active(zeros) 10.20/4.06 active(head(cons(x0, x1))) 10.20/4.06 active(tail(cons(x0, x1))) 10.20/4.06 mark(incr(x0)) 10.20/4.06 mark(nil) 10.20/4.06 mark(cons(x0, x1)) 10.20/4.06 mark(s(x0)) 10.20/4.06 mark(adx(x0)) 10.20/4.06 mark(nats) 10.20/4.06 mark(zeros) 10.20/4.06 mark(0) 10.20/4.06 mark(head(x0)) 10.20/4.06 mark(tail(x0)) 10.20/4.06 incr(mark(x0)) 10.20/4.06 incr(active(x0)) 10.20/4.06 cons(mark(x0), x1) 10.20/4.06 cons(x0, mark(x1)) 10.20/4.06 cons(active(x0), x1) 10.20/4.06 cons(x0, active(x1)) 10.20/4.06 s(mark(x0)) 10.20/4.06 s(active(x0)) 10.20/4.06 adx(mark(x0)) 10.20/4.06 adx(active(x0)) 10.20/4.06 head(mark(x0)) 10.20/4.06 head(active(x0)) 10.20/4.06 tail(mark(x0)) 10.20/4.06 tail(active(x0)) 10.20/4.06 10.20/4.06 We have to consider all minimal (P,Q,R)-chains. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (72) QReductionProof (EQUIVALENT) 10.20/4.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.20/4.06 10.20/4.06 active(incr(nil)) 10.20/4.06 active(incr(cons(x0, x1))) 10.20/4.06 active(adx(nil)) 10.20/4.06 active(adx(cons(x0, x1))) 10.20/4.06 active(nats) 10.20/4.06 active(zeros) 10.20/4.06 active(head(cons(x0, x1))) 10.20/4.06 active(tail(cons(x0, x1))) 10.20/4.06 mark(incr(x0)) 10.20/4.06 mark(nil) 10.20/4.06 mark(cons(x0, x1)) 10.20/4.06 mark(s(x0)) 10.20/4.06 mark(adx(x0)) 10.20/4.06 mark(nats) 10.20/4.06 mark(zeros) 10.20/4.06 mark(0) 10.20/4.06 mark(head(x0)) 10.20/4.06 mark(tail(x0)) 10.20/4.06 incr(mark(x0)) 10.20/4.06 incr(active(x0)) 10.20/4.06 adx(mark(x0)) 10.20/4.06 adx(active(x0)) 10.20/4.06 head(mark(x0)) 10.20/4.06 head(active(x0)) 10.20/4.06 tail(mark(x0)) 10.20/4.06 tail(active(x0)) 10.20/4.06 10.20/4.06 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (73) 10.20/4.06 Obligation: 10.20/4.06 Q DP problem: 10.20/4.06 The TRS P consists of the following rules: 10.20/4.06 10.20/4.06 MARK(s(X)) -> MARK(X) 10.20/4.06 MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.06 10.20/4.06 R is empty. 10.20/4.06 The set Q consists of the following terms: 10.20/4.06 10.20/4.06 cons(mark(x0), x1) 10.20/4.06 cons(x0, mark(x1)) 10.20/4.06 cons(active(x0), x1) 10.20/4.06 cons(x0, active(x1)) 10.20/4.06 s(mark(x0)) 10.20/4.06 s(active(x0)) 10.20/4.06 10.20/4.06 We have to consider all minimal (P,Q,R)-chains. 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (74) QDPSizeChangeProof (EQUIVALENT) 10.20/4.06 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. 10.20/4.06 10.20/4.06 From the DPs we obtained the following set of size-change graphs: 10.20/4.06 *MARK(s(X)) -> MARK(X) 10.20/4.06 The graph contains the following edges 1 > 1 10.20/4.06 10.20/4.06 10.20/4.06 *MARK(cons(X1, X2)) -> MARK(X1) 10.20/4.06 The graph contains the following edges 1 > 1 10.20/4.06 10.20/4.06 10.20/4.06 ---------------------------------------- 10.20/4.06 10.20/4.06 (75) 10.20/4.06 YES 10.46/4.08 EOF